Calculating the Private Key

Robert J. Hansen rjh at
Tue Jul 1 23:28:36 CEST 2014

> Looking at the RSA algorithm. Is it possible to calculate the private
> key when a message is available both encrypted and decrypted? Maybe not
> with just one message, but with a thousand?

Assuming you mean "RSA as used in GnuPG", it is not feasible with the
kinds of computers we know how to build.  It will take science-fiction
level breakthroughs in either engineering, mathematics, or both, to do this.

> The RSA formula for decrypting messages with RSA is – according to
> Wikipedia [1] – $ m = c^(d) (mod N) $ where N is – as a part of the
> public key – always given, c is the encrypted message, m the decrypted
> message and d the private key. Can you solve this formula for d if
> everything else is given?

Same answer as above.

> But I don‛t know how to prove it using maths :).

Nobody else does, either.  If you can prove that it's not possible to
solve the integer factorization problem in a reasonable time period,
then you'll have just proven P != NP and will be eligible for a cash
prize of a cool million dollars.  No, I'm not kidding.

The integer factorization problem (the math RSA is built upon) is
conjectured to be infeasible to break.  There is no formal proof of it,

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 455 bytes
Desc: OpenPGP digital signature
URL: </pipermail/attachments/20140701/b9212406/attachment.sig>

More information about the Gnupg-users mailing list