in All availableThis forumThis topic
 RSA question(s)
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 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
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
methodtwo
Apprentice

Joined: 01 Feb 2008
Posts: 231

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 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
John R. Graham

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.
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 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
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
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 All times are GMT Page 1 of 1

 Jump to: Select a forum Assistance----------------News & AnnouncementsFrequently Asked QuestionsInstalling GentooMultimediaDesktop EnvironmentsNetworking & SecurityKernel & HardwarePortage & ProgrammingGamers & PlayersOther Things GentooUnsupported Software Discussion & Documentation----------------Documentation, Tips & TricksGentoo ChatGentoo Forums FeedbackOff the WallDuplicate Threads International Gentoo Users----------------中文 (Chinese)DutchFinnishFrenchDeutsches Forum (German)  Diskussionsforum  Deutsche DokumentationGreekForum italiano (Italian)  Forum di discussione italiano  Risorse italiane (documentazione e tools)Polskie forum (Polish)  Instalacja i sprzęt  Polish OTWPortuguese  Documentação, Ferramentas e DicasRussianScandinavianSpanishOther Languages Architectures & Platforms----------------Gentoo on AMD64Gentoo on ARMGentoo on PPCGentoo on SparcGentoo on Alternative ArchitecturesGentoo for Mac OS X (Portage for Mac OS X)
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