# RSA question(s)

## methodtwo

Hi

Err i got rid of the original question, which is too embarrassing. I hadn't realised why phi(n) ( a property of euler's theorem as used in rsa ) was really hard to find, using any method( including trying to find all the coprimes between 1 and n-1. I hadn't thought about it properly before posting and assumed that finding all the coprimes would be more trivial than factoring n. So i missed something really obvious about rsa and then forgot about it for ages.Last edited by methodtwo on Sun Jan 24, 2016 1:18 am; edited 4 times in total

----------

## pa4wdh

I think you're pretty close with your description. RSA's strength is based on the mathematical problem of factorization, which probably is also why it's too weak when quantum computers get up to speed: https://en.wikipedia.org/wiki/Shor%27s_algorithm

If you want to know all the gory details about cryptography in general i can highly recommend the Handbook of Applied Cryptography, a strong mathematical background is recommended before reading  :Smile: 

You can find it here, chapter 8 covers RSA: http://cacr.uwaterloo.ca/hac/

----------

## methodtwo

Sorry i forgot about this momentarily. Thank you very much for your reply and the awesome link m8.

----------

## szatox

I have recently taken some time to understand how RSA works, and I noticed that while it's often said that breaking RSA is as hard as factoring modulus, it's not exactly true. And it's not true, because you don't need those 2 prime numbers to create private key. You just need to know how many sectors that ring created with your modulus N has.

Sticking to the common naming convention, once you know P and Q, you can calculate some large modulus N=P*Q and size of the ring group it will create. Ring created by a prime number P has size equal to P-1. Ring created by a composite number P*Q has size equal to E(N)=E(P)*E(Q) = (P-1)*(Q-1).

Once you have E(N) you can pick 2 numbers that will match equation D*E mod E(N) = 1. (1 because X^1=X )

This means, while factoring N would let you calculate E(N) in the same fashion you follow generating a new key pair, and finaly private key, you don't really need to know values of P and Q as they are only auxiliary values. The only private thing you do need is  E(N).

What if you could obtain E(N) in a more direct way? Factoring N would no longer be necessary. Well, I do know it's a bit funny "what if" statement, but hey, cryptography is all about "what if something goes wrong", and RSA is basicaly just running with pedometer around an ordinary ring. Yes, I am simplifying here.

RSA is briliant in it's simplicity, but still relys on "we don't know how to go around" rather than "there is no way around". So far pretty much any commonly used asymetric cryptosystem does.

BTW, since for composite N value of E(N) is less than N-1 (less than messages you can define under base N), there must be some messages that will be encoded to themselves. They are not common enough to be a problem though, even if they are a problem enough to force making keys co-prime to E(N).

Now I wonder how hard will ECC basics be  :Laughing: 

----------

## John R. Graham

What is E() here?

- John

----------

## szatox

Sorry, don't have fi on my keyboard. Euler's function, or what we are more interested in here: the size of cyclic group generated with modulus. Modulus is composite, so the group is smaller than N-1, but still way too big for brute-forcing it.

And here we go, it's like 40 years old stuff, based against all rules on a mere bellief that something is hard to reverse, and nobody claims to have broken it yet  :Wink: 

Amazing

----------

## methodtwo

Same goes for here as for the original post

----------

