23 ms·
You now know the two primes (p,q) which multiply together to make n (the public key modulus). We also know e (the public key exponent). d (the private key) is:
by alexkus 12y ago
You now know the two primes (p,q) which multiply together to make n (the public key modulus). We also know e (the public key exponent).
d (the private key) is:-
d = e^-1 mod ((p-1)(q-1))
To work this modular inverse out you use the extended Euclidean algorithm.
This is why you need to know the factorisation of n=(p*q). You can't compute d (the private key) with just the composite n.
- cryptbe 12y agoYou don't need to use p or q. See http://vnhacker.blogspot.com/2014/04/idea-to-solve-cloudflare-heartbleed.html http://vnhacker.blogspot.com/2014/04/idea-to-solve-cloudflar...
- benmmurphy 12y agoapparently these temp values are scrubbed by openssl. i would definitely verify because there could be some implementation bug that stops their scrubbing. so what nginx does is: handle_request: do_decryption scrub_temporaries write_to_client handle_another_request: .. because nginx is single threaded there shouldn't be any requests handled between do_decryption and scrub_temporaries. but this is a problem on other servers. static int RSA_eay_private_decrypt(int flen, const unsigned char *from, unsigned char *to, RSA *rsa, int padding) { ... if (ctx != NULL) { BN_CTX_end(ctx); BN_CTX_free(ctx); } if (buf != NULL) { OPENSSL_cleanse(buf,num); OPENSSL_free(buf); } return(r); void BN_CTX_free(BN_CTX *ctx) { if (ctx == NULL) return; #ifdef BN_CTX_DEBUG { BN_POOL_ITEM *pool = ctx->pool.head; fprintf(stderr,"BN_CTX_free, stack-size=%d, pool-bignums=%d\n", ctx->stack.size, ctx->pool.size); fprintf(stderr,"dmaxs: "); while(pool) { unsigned loop = 0; while(loop < BN_CTX_POOL_SIZE) fprintf(stderr,"%02x ", pool->vals[loop++].dmax); pool = pool->next; } fprintf(stderr,"\n"); } #endif BN_STACK_finish(&ctx->stack); BN_POOL_finish(&ctx->pool); OPENSSL_free(ctx); } static void BN_POOL_finish(BN_POOL *p) { while(p->head) { unsigned int loop = 0; BIGNUM *bn = p->head->vals; while(loop++ < BN_CTX_POOL_SIZE) { if(bn->d) BN_clear_free(bn); bn++; } p->current = p->head->next; OPENSSL_free(p->head); p->head = p->current; } } void BN_clear_free(BIGNUM *a) { int i; if (a == NULL) return; bn_check_top(a); if (a->d != NULL) { OPENSSL_cleanse(a->d,a->dmax*sizeof(a->d[0])); if (!(BN_get_flags(a,BN_FLG_STATIC_DATA))) OPENSSL_free(a->d); } i=BN_get_flags(a,BN_FLG_MALLOCED); OPENSSL_cleanse(a,sizeof(BIGNUM)); if (i) OPENSSL_free(a); } void OPENSSL_cleanse(void *ptr, size_t len) { unsigned char *p = ptr; size_t loop = len, ctr = cleanse_ctr; while(loop--) { *(p++) = (unsigned char)ctr; ctr += (17 + ((size_t)p & 0xF)); } p=memchr(ptr, (unsigned char)ctr, len); if(p) ctr += (63 + (size_t)p); cleanse_ctr = (unsigned char)ctr; }
- cryptbe 12y agoYeah, you're correct. So it seems that you don't need math to solve this challenge, but maybe luck and patience.
- dogsky 12y agoVery interesting. So, just with the private key given p/q and the modulus is really possible to extract the private key? I saw the RSATool (https://github.com/ius/rsatool https://github.com/ius/rsatool), but it needs an "n" and "d" parameter. So, how to use the output from this modified hertbeet exploit with RSATool since it only prints "Using Modulus", "Got result:" and "Found Prime" and all are much larger in comparison with parameters for RSATOOL. Thanks.
- quasque 12y agoIf you have modulus n and prime p, you can get the other prime q by dividing n by p. This gives you both primes, which is the input to RSA key generation (along with the public exponent which is usually 65537, but can be extracted from the X.509 certificate along with the modulus).