﻿ New RSA Algorithm discussion
18 May, 2013, 16:32:24
 OmnomIRC You must Register, be logged in and have at least 40 posts to use this shout-box! If it still doesn't show up afterward, it might be that OmnomIRC is disabled for your group or under maintenance.Note: You can also use an IRC client like mIRC, X-Chat or Mibbit to connect to an EFnet server and #omnimaga.

 Pages: [1] 2 3 ... 14   Go Down
 Author Topic: New RSA Algorithm discussion -  (Read 12765 times) 0 Members and 1 Guest are viewing this topic.
graphmastur
King Graphmastur
LV11 Super Veteran (Next: 3000)

Offline

Gender:
Last Login: 02 February, 2013, 08:34:45
Date Registered: 03 June, 2010, 21:15:55
Posts: 2262

Topic starter
Total Post Ratings: +60

 « on: 21 July, 2010, 17:41:58 » +4

Okay, so many people want to break RSA security because of the Nspire.  Well, it's not at all easy, and the current algorithms won't even work well on a 1024 bit number.  So I was thinking, that if an entire calculator community put their heads together, then we might actually think of a workable algorithm.  Now then, first I will explain RSA.

RSA is a public/private key cryptography system.  You have a public key (n,e) and a private key (n,d).  When you "break" RSA, it means that you found the private key using the public key.  Now then, I will show you how you get n, d, and e, and why it is so difficult to break as n grows larger.

The basis of the algorithm is simple.  You find two prime numbers, p and q, that are somewhat close together (about the same bit-length).  You set n=pq.  Now, n is a semi-prime, which means it is a multiple of two primes.  You then choose an e (most common one is 65537 or 2^16+1).  You find the totient function (which in the case of primes is p-1), so you set t=(p-1)(q-1).  Now you use an algorithm (Extended Euclidean) to find d such that de-1 is divisible by t.

With the Nspire keys, we have the public key: n and the exponent (most likely 65537, but that doesn't really matter), and we need to find the private key: n and d.

Finding d using e and the totient is easy.  The question is how to find the totient from n.  Well, the most obvious method would be to factor the number n, and use the factors, p and q, to find the toitent function (p-1)(q-1).  Now then, I believe an example is in order.  (Note: The number used here is not even close to the size of the actual numbers used.)

This is done as if we were TI, making the keys for the initial use.
Say we choose two prime numbers. p=13 and q=17.  We can easily see that (13-1)(17-1)=(12)(16)=192=t.  Now, using the Extended Euclidean algorithm, we use e=65537 and t to find d.  This makes d=65.  In case you don't want to read the Extended Euclidean algorithm (Specifically modular multiplicative inverse), let me explain how it works.  de-1=(65)(65537)-1=4259905-1=4259904.  4259904/192=22187, with the remainder being 0.  This is the d for the private key.  We are done finding the keys to use.

TI can either encrypt or sign their OS.  What signing means, is that a checksum of the data of the OS is taken, and encrypted using the private key.  (That is done one the computer)  The calc then does a checksum of the os, and uses it's public key to decrypt the checksum of the OS.  If the two checksums are equal, it is a valid os sent by TI.

Now then, this is our part:
The easiest way to send an OS or open the calc completely would be to, using the public key (which we already have) factor the number n.  Using the factors, we can easily find the private key.  The number 221 that I used earlier is only a byte.  That is 8 bits.  The number we are trying to factor for the Nspire is 1024 bits.  That is a lot bigger, so there are a few things that won't work:

• Naive algorithms like trial division. (Seriously, please don't suggest it)
• Any current algorithm.  Yep, no current algorithm is good enough to factor the key.  The current record is 768 bits, made by the top researchers with algorithms we don't even have access to.
Have I made it seem like all hope is lost?  Good! Now then, the reason I am creating this thread is not to discourage, but encourage.  I believe that if we all work on an algorithm together, that it is possible to actually factor the numbers.

(I just realized that I use the phrase "now then," a lot when trying to explain something.)

Any questions  (Wow, that was a long post with a lot of parenthesis.)
 Logged

DJ Omnimaga
Retired Omnimaga founder (Site issues must be PM'ed to Netham45, Eeems, Shmibs, Deep Thought and AngelFish, not me.)
Editor
LV15 Omnimagician (Next: --)

Offline

Gender:
Date Registered: 25 August, 2008, 07:00:21
Posts: 50196

Total Post Ratings: +2611

 « Reply #1 on: 21 July, 2010, 17:44:40 » 0

Wow thanks for the explanation. Hopefully it should help people into understanding the concept a bit. One concern I have, though: If we factored the key, could TI release a new line of Nspires that uses a totally different key as a counter-attack or something?
 Logged

Retired 83+ coder, Omnimaga/TIMGUL founder. Now doing power metal music (formerly did electronica)

calcdude84se
Needs Motivation
Members
LV11 Super Veteran (Next: 3000)

Offline

Gender:
Last Login: 14 May, 2013, 16:12:14
Date Registered: 21 April, 2010, 04:20:59
Posts: 2207

Total Post Ratings: +62

 « Reply #2 on: 21 July, 2010, 17:48:44 » 0

Yes, but while they supported the old ones they'd have to release two copies of each OS, one for each key.
So either they'd drop the old one immediately (probably not) or they'd release two of each OS (possible, but I'm sure TI doesn't want to put their customers through figuring out which revision they have )
We're probably safe.
Thanks for the explanation, graphmastur! I do wonder if we could find a better way...
 Logged

"People think computers will keep them from making mistakes. They're wrong. With computers you make mistakes faster."
Bug me about PartesOS. I might just need reminding.
quasi_Phthalo
LV3 Member (Next: 100)

Offline

Last Login: 26 August, 2010, 22:44:51
Date Registered: 17 June, 2010, 20:52:42
Posts: 85

Total Post Ratings: 0

 « Reply #3 on: 21 July, 2010, 17:50:26 » 0

the reason we need to factor n into p*q is so that we can calculate phi(n)=(p-1)*(q-1), right? well, what if, instead of trying to find a better factoring algorithm, we try to find a fast way to compute the totient without knowing the factors.....
 Logged
calcdude84se
Needs Motivation
Members
LV11 Super Veteran (Next: 3000)

Offline

Gender:
Last Login: 14 May, 2013, 16:12:14
Date Registered: 21 April, 2010, 04:20:59
Posts: 2207

Total Post Ratings: +62

 « Reply #4 on: 21 July, 2010, 17:52:30 » 0

That's another way to look at it.
And for those who don't know, the totient function returns how many natural number less than another natural number are relatively prime to it (i.e. no common factors) 1 is considered relatively prime to all natural numbers.
 Logged

"People think computers will keep them from making mistakes. They're wrong. With computers you make mistakes faster."
Bug me about PartesOS. I might just need reminding.
graphmastur
King Graphmastur
LV11 Super Veteran (Next: 3000)

Offline

Gender:
Last Login: 02 February, 2013, 08:34:45
Date Registered: 03 June, 2010, 21:15:55
Posts: 2262

Topic starter
Total Post Ratings: +60

 « Reply #5 on: 21 July, 2010, 17:56:44 » 0

I hope we can find another way.  I don't fully understand the Nspire, so this is my way of contributing.  Also, I have one concern. If they can prevent another OS, like below a certain version, then there must be a way to prevent other non-ti os as well.  Basically, if we factor the boot2 key, we shouldn't have any problem at all.

Although, they would not have to do a whole new line, necessarily.  They would just need to change the keys on all new versions.  Also, if the system supported it, technically, the os could have many signatures, all signed with different keys, and if the any/all of the keys matched, it was accepted.  I don't know how effective that would be, though, as you are signing the same hash with different keys.
 Logged

t0xic_kitt3n
LV10 31337 u53r (Next: 2000)

Offline

Gender:
Last Login: 13 May, 2013, 01:56:35
Date Registered: 16 June, 2010, 20:46:00
Location: w,x,y,z
Posts: 1583

Total Post Ratings: +32

 « Reply #6 on: 21 July, 2010, 18:12:12 » 0

When does the OS get validated? At each boot, or just when it is installed?
 Logged

██████  ██  ██  ███████           ████    ██    ██   ██ ███████
█ ██ █  ██  ██   ██   █          ██  ██  ████   ███ ███  ██   █
██    ██  ██   ██             ██   ██ ██  ██  ███████  ██
██    ██  ██   ██  █         ██       ██  ██  ███████  ██  █
██    ██████   █████         ██       ██  ██  ██ █ ██  █████
██    ██  ██   ██  █         ██   ███ ██████  ██   ██  ██  █
██    ██  ██   ██             ██   ██ ██  ██  ██   ██  ██
██    ██  ██   ██   █          ██  ██ ██  ██  ██   ██  ██   █
████   ██  ██  ███████           █████ ██  ██  ██   ██ ███████

graphmastur
King Graphmastur
LV11 Super Veteran (Next: 3000)

Offline

Gender:
Last Login: 02 February, 2013, 08:34:45
Date Registered: 03 June, 2010, 21:15:55
Posts: 2262

Topic starter
Total Post Ratings: +60

 « Reply #7 on: 21 July, 2010, 18:14:48 » 0

I believe it is when it is installed. And no "let's modify the OS" comments, please, btw.  I think Ndless should do fine for that, while this thread is for RSA. Just a precaution.

Oh, and I didn't realize it before, but I definitely got Ninja'd on my last post.

the reason we need to factor n into p*q is so that we can calculate phi(n)=(p-1)*(q-1), right? well, what if, instead of trying to find a better factoring algorithm, we try to find a fast way to compute the totient without knowing the factors.....
We could.  The difference between n and t is (P+Q-1), though.
 « Last Edit: 21 July, 2010, 18:16:10 by graphmastur » Logged

graphmastur
King Graphmastur
LV11 Super Veteran (Next: 3000)

Offline

Gender:
Last Login: 02 February, 2013, 08:34:45
Date Registered: 03 June, 2010, 21:15:55
Posts: 2262

Topic starter
Total Post Ratings: +60

 « Reply #8 on: 22 July, 2010, 03:35:10 » 0

Okay, so I noticed something with things mod 4. This table is done mod 4.  eg, 13 mod 4=1.
 p q n 1 1 1 1 3 3 3 1 3 3 3 1

So in other words, if n mod 4=3, then the number is of the form (4x+1)(4y+3)=16xy+12x+4y+3.  You can graph it, but I know of no way to solve this over the integers.  Any ideas?

[EDIT] oh, and sorry for the double post.
[EDIT2]  See post by me a few posts down for a better explanation.  Post fixed here.
 « Last Edit: 22 July, 2010, 04:58:42 by graphmastur » Logged

calcdude84se
Needs Motivation
Members
LV11 Super Veteran (Next: 3000)

Offline

Gender:
Last Login: 14 May, 2013, 16:12:14
Date Registered: 21 April, 2010, 04:20:59
Posts: 2207

Total Post Ratings: +62

 « Reply #9 on: 22 July, 2010, 03:36:59 » 0

I'm not sure if this can be generalized to higher moduli. If it can, it might not be pretty.
 Logged

"People think computers will keep them from making mistakes. They're wrong. With computers you make mistakes faster."
Bug me about PartesOS. I might just need reminding.
graphmastur
King Graphmastur
LV11 Super Veteran (Next: 3000)

Offline

Gender:
Last Login: 02 February, 2013, 08:34:45
Date Registered: 03 June, 2010, 21:15:55
Posts: 2262

Topic starter
Total Post Ratings: +60

 « Reply #10 on: 22 July, 2010, 03:40:07 » 0

I'm not sure if this can be generalized to higher moduli. If it can, it might not be pretty.
Why would it be generalized to higher moduli? 4 is all that is necessary, and I believe it works on all numbers.  Besides, if you solve the equation above over the integers, then there is only one solution.

Can you please explain what you mean a little better?
 Logged

qazz42
LV9 Veteran (Next: 1337)

Offline

Last Login: 29 December, 2012, 01:39:31
Date Registered: 19 June, 2010, 16:06:31
Posts: 1134

Total Post Ratings: +17

 « Reply #11 on: 22 July, 2010, 03:41:09 » 0

What TI needs is an eternity code, that might shut us up
 Logged

calcdude84se
Needs Motivation
Members
LV11 Super Veteran (Next: 3000)

Offline

Gender:
Last Login: 14 May, 2013, 16:12:14
Date Registered: 21 April, 2010, 04:20:59
Posts: 2207

Total Post Ratings: +62

 « Reply #12 on: 22 July, 2010, 03:41:43 » 0

Maybe you could explain it a bit better?
 Logged

"People think computers will keep them from making mistakes. They're wrong. With computers you make mistakes faster."
Bug me about PartesOS. I might just need reminding.
graphmastur
King Graphmastur
LV11 Super Veteran (Next: 3000)

Offline

Gender:
Last Login: 02 February, 2013, 08:34:45
Date Registered: 03 June, 2010, 21:15:55
Posts: 2262

Topic starter
Total Post Ratings: +60

 « Reply #13 on: 22 July, 2010, 03:47:27 » 0

Okay, well take any n which is a semiprime and do mod 4 of it.  eg, the remainder when it is divided by 4.  So if I have p=13 and q=19, that means p mod 4=1 and q mod 4=3, so pq mod 4=3.  That means that if we have an n, where n mod 4=3, it either means the p mod 4=3 or q mod 4=3, and the other mod 4 =1.

There is one thing I messed up, though.  It is supposed to be (4x+1)(4y+3)=16xy+12x+4y+3.  I'll go fix that in my last post...  Basically, though, if you solve that over the integers, it yields the factors.  There is only one solution.
 « Last Edit: 22 July, 2010, 04:58:30 by graphmastur » Logged

bwang
LV7 Elite (Next: 700)

Offline

Last Login: 11 August, 2012, 12:59:06
Date Registered: 20 June, 2009, 01:42:58
Posts: 632

Total Post Ratings: +19

 « Reply #14 on: 22 July, 2010, 04:45:26 » 0

the reason we need to factor n into p*q is so that we can calculate phi(n)=(p-1)*(q-1), right? well, what if, instead of trying to find a better factoring algorithm, we try to find a fast way to compute the totient without knowing the factors.....
No. Computing phi(n) is polynomial-time equivalent to factoring n. It is generally accepted that the two problems are equally hard.
Okay, well take any n which is a semiprime and do mod 4 of it.  eg, the remainder when it is divided by 4.  So if I have p=13 and q=19, that means p mod 4=1 and q mod 4=3, so pq mod 4=3.  That means that if we have an n, where n mod 4=3, it either means the p mod 4=3 or q mod 4=3, and the other mod 4 =1.

There is one thing I messed up, though.  It is supposed to be (4x+1)(4y+3)=16xy2+12x+4y+3.  I'll go fix that in my last post...  Basically, though, if you solve that over the integers, it yields the factors.  There is only one solution.
Why 16*x*y^2? I think its 16xy.
---------------------------------------------------------------------------------------------------------------------
I believe the factorization of RSA-768 used the NFS. If we were really crazy, we could try writing an implementation of the NFS that is faster than what we currently have (GGNFS + Msieve).
Number field sieves are hard to write It would be an interesting community project, though.
 Logged
 Pages: [1] 2 3 ... 14   Go Up