View previous topic :: View next topic 
Author 
Message 
methodtwo Apprentice
Joined: 01 Feb 2008 Posts: 231

Posted: Wed Apr 22, 2015 6:58 pm Post subject: RSA question(s) 


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 n1. 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 

Back to top 


pa4wdh Guru
Joined: 16 Dec 2005 Posts: 362

Posted: Thu Apr 23, 2015 5:32 pm Post subject: 


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
You can find it here, chapter 8 covers RSA: http://cacr.uwaterloo.ca/hac/ _________________ The gentoo way of bringing peace to the world:
USE="war" emerge newuse @world
Free as in Freedom is not limited to software only:
Music: http://www.jamendo.com
Recipes: http://www.opensourcefood.com 

Back to top 


methodtwo Apprentice
Joined: 01 Feb 2008 Posts: 231

Posted: Sat Apr 25, 2015 11:21 pm Post subject: 


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

Back to top 


szatox Veteran
Joined: 27 Aug 2013 Posts: 1879

Posted: Sat May 23, 2015 12:09 pm Post subject: 


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 P1. Ring created by a composite number P*Q has size equal to E(N)=E(P)*E(Q) = (P1)*(Q1).
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 N1 (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 coprime to E(N).
Now I wonder how hard will ECC basics be 

Back to top 


John R. Graham Administrator
Joined: 08 Mar 2005 Posts: 10459 Location: Somewhere over Atlanta, Georgia

Posted: Sat May 23, 2015 6:52 pm Post subject: 


What is E() here?
 John _________________ I can confirm that I have received between 0 and 499 National Security Letters. 

Back to top 


szatox Veteran
Joined: 27 Aug 2013 Posts: 1879

Posted: Sat May 23, 2015 8:19 pm Post subject: 


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 N1, but still way too big for bruteforcing 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
Amazing 

Back to top 


methodtwo Apprentice
Joined: 01 Feb 2008 Posts: 231

Posted: Wed Jun 24, 2015 3:58 am Post subject: 


Same goes for here as for the original post 

Back to top 


