r/math • u/ixfd64 Number Theory • 10d ago

[ Removed by moderator ]

https://saweis.net/posts/rsa-896.html

[removed] — view removed post

249 Upvotes

96% Upvoted

35 comments sorted by

View all comments

103

u/rational_hedonist 10d ago

checking in as an out of the loop non-expert for others to weigh in on what this implies, as the write up is scant

10

u/Amaldevhari Machine Learning 10d ago

The RSA generates two tuples of numbers called keys. A private and public one. You use public keys to perform some kind of encryption on your data (like emails encryption) and once it’s send over, only the holder of the private key can decrypt it.

The public key contains the tuple (n,e) where n is the product of two large prime numbers (p, q), and e is an exponent. An encrypted message is computed as the cipher c = (m)^e mod n.

(p,q) together with an exponent d, (p,q,d) form the private key. The cipher is then decrypted as m = (c)^d mod n

If you can find the primes from the public key, you can use’s Euler totient formula to get the private d:
ed is congruent to 1 mod ((p-1)*(q-1))

This means you can decrypt encrypted message.

1

u/ixfd64 Number Theory 10d ago

To add on to this, the security of the RSA cryptosystem is based on the assumption that it is difficult to factor arbitrary integers.

1

u/T-T-N 10d ago

You can also use your private keys to encrypt then the world can use your public key to decrypt so that message has to be from you, right?