Gentoo Forums
Gentoo Forums
Gentoo Forums
Quick Search: in
RSA question(s)
View unanswered posts
View posts from last 24 hours

 
Reply to topic    Gentoo Forums Forum Index Networking & Security
View previous topic :: View next topic  
Author Message
methodtwo
Apprentice
Apprentice


Joined: 01 Feb 2008
Posts: 231

PostPosted: Wed Apr 22, 2015 6:58 pm    Post subject: RSA question(s) Reply with quote

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
Back to top
View user's profile Send private message
pa4wdh
Guru
Guru


Joined: 16 Dec 2005
Posts: 316

PostPosted: Thu Apr 23, 2015 5:32 pm    Post subject: Reply with quote

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
View user's profile Send private message
methodtwo
Apprentice
Apprentice


Joined: 01 Feb 2008
Posts: 231

PostPosted: Sat Apr 25, 2015 11:21 pm    Post subject: Reply with quote

Sorry i forgot about this momentarily. Thank you very much for your reply and the awesome link m8.
Back to top
View user's profile Send private message
szatox
Veteran
Veteran


Joined: 27 Aug 2013
Posts: 1762

PostPosted: Sat May 23, 2015 12:09 pm    Post subject: Reply with quote

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 :lol:
Back to top
View user's profile Send private message
John R. Graham
Administrator
Administrator


Joined: 08 Mar 2005
Posts: 10342
Location: Somewhere over Atlanta, Georgia

PostPosted: Sat May 23, 2015 6:52 pm    Post subject: Reply with quote

What is E() here?

- John
_________________
I can confirm that I have received between 0 and 499 National Security Letters.
Back to top
View user's profile Send private message
szatox
Veteran
Veteran


Joined: 27 Aug 2013
Posts: 1762

PostPosted: Sat May 23, 2015 8:19 pm    Post subject: Reply with quote

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 ;)
Amazing
Back to top
View user's profile Send private message
methodtwo
Apprentice
Apprentice


Joined: 01 Feb 2008
Posts: 231

PostPosted: Wed Jun 24, 2015 3:58 am    Post subject: Reply with quote

Same goes for here as for the original post
Back to top
View user's profile Send private message
Display posts from previous:   
Reply to topic    Gentoo Forums Forum Index Networking & Security All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum