Print Page - New RSA Algorithm discussion

General Discussion => Other Discussions => Math and Science => Topic started by: jnesselr on July 21, 2010, 11:41:58 am

Title: New RSA Algorithm discussion
Post by: jnesselr on July 21, 2010, 11:41:58 am

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

Title: Re: New RSA Algorithm discussion
Post by: DJ Omnimaga on July 21, 2010, 11:44:40 am

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?

Title: Re: New RSA Algorithm discussion
Post by: calcdude84se on July 21, 2010, 11:48:44 am

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 :P)
We're probably safe.
Thanks for the explanation, graphmastur! I do wonder if we could find a better way...

Title: Re: New RSA Algorithm discussion
Post by: quasi_Phthalo on July 21, 2010, 11:50:26 am

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

Title: Re: New RSA Algorithm discussion
Post by: calcdude84se on July 21, 2010, 11:52:30 am

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.

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on July 21, 2010, 11:56:44 am

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.

Title: Re: New RSA Algorithm discussion
Post by: fb39ca4 on July 21, 2010, 12:12:12 pm

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

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on July 21, 2010, 12:14:48 pm

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. :D

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

Quote from: quasi_Phthalo on July 21, 2010, 11:50:26 am

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.

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on July 21, 2010, 09:35:10 pm

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.

Title: Re: New RSA Algorithm discussion
Post by: calcdude84se on July 21, 2010, 09:36:59 pm

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

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on July 21, 2010, 09:40:07 pm

Quote from: calcdude84se on July 21, 2010, 09:36:59 pm

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?

Title: Re: New RSA Algorithm discussion
Post by: qazz42 on July 21, 2010, 09:41:09 pm

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

Title: Re: New RSA Algorithm discussion
Post by: calcdude84se on July 21, 2010, 09:41:43 pm

I guess I didn't read it well enough, my bad :(
Maybe you could explain it a bit better?

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on July 21, 2010, 09:47:27 pm

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.

Title: Re: New RSA Algorithm discussion
Post by: bwang on July 21, 2010, 10:45:26 pm

Quote from: quasi_Phthalo on July 21, 2010, 11:50:26 am

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.

Quote from: graphmastur on July 21, 2010, 09:47:27 pm

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.

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.

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on July 21, 2010, 10:59:53 pm

You are correct. I fixed it in both posts. Also, the sieve would require a huge amount of space for it, and I barely understand the concepts in a sieve like this. The idea of this thread was to create better alternatives for the current algorithms, so what are your ideas to make it faster?

Title: Re: New RSA Algorithm discussion
Post by: quasi_Phthalo on July 21, 2010, 11:20:27 pm

Quote

Computing phi(n) is polynomial-time equivalent to factoring n. It is generally accepted that the two problems are equally hard.

"equally hard" in the sense of "the only way we know HOW to find phi(n) is to factor n, hence, they take the same amount of time". But i'm suggesting to find a different way to find phi(n)

so, this key is 1024 bits, right? Is the first bit a 0 or a 1? In other words, is the 1024 just a general size, slash, does starting with a 0 made it a 1023 bit number....?

Title: Re: New RSA Algorithm discussion
Post by: Tribal on July 21, 2010, 11:47:37 pm

The amount of bits can be seen by 2^n where 'n' is the amount of bits a number is.
8-bit: 2^8=256
16-bit: 2^16=65536
etc...

EDIT: The result refers to the largest possible number that the bit can hold.

Title: Re: New RSA Algorithm discussion
Post by: quasi_Phthalo on July 21, 2010, 11:52:49 pm

right, but, the number 120, for example, would fall under the class of 1-byte (8-bit) integers because that's the size of register you would most likely put it in, even though it technically only takes up 7 bits.
i was wondering specifically, is the key exactly 1024 bits long, with the first bit a 1?

Title: Re: New RSA Algorithm discussion
Post by: bwang on July 22, 2010, 12:56:31 am

Quote from: quasi_Phthalo on July 21, 2010, 11:20:27 pm

Quote
Computing phi(n) is polynomial-time equivalent to factoring n. It is generally accepted that the two problems are equally hard.
"equally hard" in the sense of "the only way we know HOW to find phi(n) is to factor n, hence, they take the same amount of time". But i'm suggesting to find a different way to find phi(n)

"Equally hard" as in find phi(n) would allow us to factor n too.

Quote

The idea of this thread was to create better alternatives for the current algorithms, so what are your ideas to make it faster?

A new algorithm that is asymptotically faster than the NFS would be a monumental achievement. The top researchers in the field have been working on it for a couple decades now, and so far no they've had no luck.
If you want to start building a new algorithm, its best to look at the current ones first. In case anyone is interested, here is a summary of the Quadratic Sieve, the (slower) predecessor to the NFS. It uses the same ideas, but is much, much simpler (no prime ideals, rings of algebraic integers, etc., just good old integers!).

The Quadratic Sieve
Let n be the number we are attempting to factor. The gist of the QS (and the NFS) is to find x^2 = y^2 (mod n) with x and y integers. Then we may compute gcd(x - y, n) and gcd(x + y, n), which each has a high probability of being a nontrivial factor of n.
But how do we find such x and y? That is what the algorithm does.
We define a factor base F = {p_1, p_2, ... p_k} to be the set of all primes less than or equal to some predetermined bound B. Let f(x) = x^2 - n. Let I be the set of integers contained in the interval [sqrt(n), sqrt(n) + M] for some predetermined bound M. Finally, we say that an integer m in I is smooth over F if all prime factors of m are in F.
Step 1: Sieving
The sieving step tries to find k integers a_1, a_2, a_3, ... a_k in I such that f(a_i) is smooth over F for all i = 1, 2, ... k. It works as follows:
*Initialize an array T to the values of f(a), where a is in the interval I.
*For each prime p in F:
   *Find solutions x0, x1 to the congruence x^2 = n (mod p) using the Shanks-Tonelli algorithm.
   *Divide the elements of T corresponding to x0 + t * p, x1 + t * p (t is an integer) by the largest value of p that divide them. Note that since
   x0, x1 satisfy x^2 = n (mod p), f(x0 + t * p) and f(x1 + t * p) are divisible by p. Indeed, the are the only elements of T divisible by p.
*Store the values of f corresponding to those elements of T that are now 1 into an array R. The elements of R are precisely those values of f(a) that
  are smooth over F.
Step 2: Linear algebra
*We now have {a_1, a_2, ... a_k} with f(a_i) smooth over F. We want to find a subset of the f(a_i) such that their product is a square.
*To so, write f(a_i) = p_1^e_i1 * p_2^e_i2 * ... * p_k^e_ik. Associate with a_i the binary vector A_i = (e_i1 % 2, e_i2 % 2, ... e_ik % 2). If we can
find a binary vector (c_1, c_2, ... c_k) such that sum (c_i * A_i) = (0, 0, 0, ...0) mod 2, we'd have our subset. This is because the product of the
a_i corresponding to those c_i that are 1 would have the property that the exponent of each p_i is even.
*Now let the matrix A = [A_1, A_2, ...A_k] (we are placing the column representations of the A_i side by side to form A). A moment's thought shows
  that finding the c_i corresponds to solving the system A * C = 0. This is a well known problem from linear algebra, and can be solved with Gaussian
elimination or the Lanczos algorithm.
*When all is said and done, we have our subset of the a_i. Call these {b_1, b_2, ... b_m}.
Step 3: Finding x and y
*We simply let x = b_1 * b_2 * ... * b_m and y = sqrt(f(b_1) * f(b_2) * ... * f(b_m)). By the definition of the b_i and f, y is an integer, and x^2 =
  y^2 (mod n)
*We have x and y, so we can factor n!

Title: Re: New RSA Algorithm discussion
Post by: mapar007 on July 22, 2010, 04:05:54 am

Quote from: quasi_Phthalo on July 21, 2010, 11:20:27 pm

Quote
Computing phi(n) is polynomial-time equivalent to factoring n. It is generally accepted that the two problems are equally hard.
"equally hard" in the sense of "the only way we know HOW to find phi(n) is to factor n, hence, they take the same amount of time". But i'm suggesting to find a different way to find phi(n)

That would require a major breakthrough in number theory, not in algorithm study ;)

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on July 22, 2010, 08:43:37 am

You are correct Mapar007, AFAIK.

@bwang. Thank you for explaining that, I think the quadratic sieve will help. quick question,though. Do you mind explaining what the difficult part or what part takes the most time is? eg. why is it ineffective?

Title: Re: New RSA Algorithm discussion
Post by: bwang on July 22, 2010, 04:13:07 pm

The most time-consuming step of the QS is the sieving step. The NFS improves upon it by using a different, more complicated sieving method.
The matrix step for the QS and the NFS use the same algorithm, which, unfortunately, cannot be easily distributed over a network.

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on July 22, 2010, 10:39:22 pm

Thank you Bwang, for that information.

I thought about a recursive algorithm that finds the factors, but have no idea how it would be done. It would stop once it found p or q, but where to start. Obviously, we are talking about integers, here. (eg, not decimals or fractions) Any ideas?

Title: Re: New RSA Algorithm discussion
Post by: Lionel Debroux on July 23, 2010, 03:01:40 am

Quote

The matrix step for the QS and the NFS use the same algorithm, which, unfortunately, cannot be easily distributed over a network.

Indeed, at least for problems of the size we're talking about (GNFS difficulty 310 >> state of the art).
For smaller problems, jasonp recently added MPI support to msieve, and smaller problems sail on a cluster of Infiniband-connected nodes (i.e. not everyone's average PC): http://www.mersenneforum.org/showthread.php?t=13550

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on July 23, 2010, 11:17:33 am

So can the matrix be done over a network type thing? Can you explain Tonelli-Shanks algorithm or give a link to a better article than wikipedia?

Basically, though, if we could solve the matrix over a network of computers, would it be more efficient for these numbers? eg. not take forever?

Title: Re: New RSA Algorithm discussion
Post by: Lionel Debroux on July 23, 2010, 11:47:11 am

Yes, it can be done over a network, that's what they did for RSA-768. It's hard and it scales sub-linearly.

I know nothing about how the integer factoring algorithms work :D
(yes, I'm serious, I'm managing a moderate-size integer factoring grid and I don't know how the algorithms work. I don't really need to)

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on July 23, 2010, 01:36:47 pm

You have no idea how they work, and yet you host a grid. Wow. Wait, grid? what Grid?

Anyway, yeah, so what did you think of the recursive idea? Is it possible?

Title: Re: New RSA Algorithm discussion
Post by: Lionel Debroux on July 23, 2010, 01:45:58 pm

The RSALS grid, which started for speeding up the factorization of the 512-bit RSA keys of TI-Z80 and TI-68k calculators, and has, after those factorizations, switched to integers of mathematical interest :)
I'm not the owner of the server, but I'm the one feeding the grid with numbers, nowadays using the Web interface done by the owner. See http://boinc.unsads.com/rsals/crunching.php for more information.

And I frankly have zero idea about your idea, sorry :(

Title: Re: New RSA Algorithm discussion
Post by: matthias1992 on July 23, 2010, 04:54:18 pm

Either I am a genius or I entirely misunderstand the concept of factoring but I managed to yesterday crack a 32 bit key on my calculator under a second. I think I entirely misunderstand the whole RSA encryption technology :(

well if I am back home (where I have boinc) I'll usrely support the project.

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on July 23, 2010, 04:54:56 pm

Oh, I see. What about the idea to use boinc to study the relationships between semiprimes and their factors?

Is it possible? (I mean I know that it is, but could WE do it?)

Title: Re: New RSA Algorithm discussion
Post by: Builderboy on July 23, 2010, 04:55:27 pm

What method did you use?

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on July 23, 2010, 04:56:17 pm

Yes, Matthias, what method did you use?

Oh, and ninja'd in my last post.

Title: Re: New RSA Algorithm discussion
Post by: calcdude84se on July 23, 2010, 04:59:34 pm

32 bits is only up to ~4 billion. Not a lot.
1024 bits, on the other hand, goes up to 5e30, or 5 nonillion.
The problem is that, at least with TF, the time increases exponentially.
You're not misunderstanding it, you underestimating how quickly an exponential function grows.

Title: Re: New RSA Algorithm discussion
Post by: Builderboy on July 23, 2010, 05:04:29 pm

Ah that would be the reason. Mathias what language did you use to do this?

Title: Re: New RSA Algorithm discussion
Post by: calcdude84se on July 23, 2010, 05:05:35 pm

I would guess Axe, but he might've used ASM. Definitely not BASIC ;D

Title: Re: New RSA Algorithm discussion
Post by: Builderboy on July 23, 2010, 05:09:20 pm

If it was Basic i would have definetaly wanted to see *that* code ;D

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on July 23, 2010, 05:09:58 pm

Oh yes. That would be amazing.

Title: Re: New RSA Algorithm discussion
Post by: matthias1992 on July 23, 2010, 05:49:45 pm

Nah ignore my post, I took a entirely wrong aproach. It was asm btw. I am now studying Euclides algorithm. Shouldn't be too hard to write a asm/vb/c program for. I only have trouble with the last step of the RSA encryption/decryption. I dont understand mod(). Well hopefully someone can explain in layman's language. What I did in my program was just brute forcing every possibilty until a match was found. That match however wasn't encrypted at all. Sorry for the false excitiment. If you don't get my rough explanation of my program just leave it be, it didn't do the trick anyway. I really want to crack this code! :P

eternal fame awaits :D

edit:

Quote from: Builderboy on July 23, 2010, 05:09:20 pm

If it was Basic i would have definetaly wanted to see *that* code ;D

Code: [Select]

Input "Secret Code:", A
Disp "Code cracked!", "isn't it:",A

somtimes things are really that easy :P

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on July 23, 2010, 06:29:22 pm

Um, not quite. It doesn't actually need to be encrypted or anything. To break the algorithm, you must simply factor the number (which is more difficult the longer it is.)

N mod S means the remainder of N divided by S.

Title: Re: New RSA Algorithm discussion
Post by: bwang on July 23, 2010, 08:57:59 pm

@graphmastur: I will try to explain the algorithm:

Shanks-Tonelli modular square root algorithm:
The problem: given n and p, with p prime, find x such that x^2 = n (mod p)
First, a digression. The Legendre symbol (n|p) (actually written in a different manner, but the forum does not support typesetting) is defined as follows: (n|p) = 1 if such an x exists, 0 if p divides n, and -1 otherwise. It can be computed as n^((p-1)/2) mod p.
Now we return to the algorithm:
Step 1: Let p - 1 = 2^s * q , with q odd. This can be done by dividing powers of 2 out of p - 1 until we cannot do so any further.
Step 2: Select z such that (z|p) = -1. We do this simply by randomly selecting z in the set {1, 2, ... p - 1} and computing (z|p) as described above.
Step 3: Let:
c = z^q mod p
r = n^((q + 1) / 2) mod p
t = n^q mod p
m = s
Note that all of these values can be computed rapidly using the repeated squaring algorithm.
Step 4: We execute the following loop:
While t != 1
i = 0
tmp = t mod p
While tmp != 1
tmp = tmp * tmp mod p
i = i + 1
EndWhile
b = c
For k = 1 to m - i - 1
b = b * b mod p
EndFor
r = r * b mod p
t = t * b^2 mod p
c = b^2 mod p
m = i
EndWhile
Step 5: Return r

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on July 23, 2010, 09:54:31 pm

Thank you so much. That is a lot easier to understand than wikipedia. Also, I somewhat understand quadratic residues.

Title: Re: New RSA Algorithm discussion
Post by: Lionel Debroux on July 24, 2010, 02:26:51 am

Quote

1024 bits, on the other hand, goes up to 5e30, or 5 nonillion.

Actually, ~1.8e308, with factors up to ~1.3e154.

Title: Re: New RSA Algorithm discussion
Post by: matthias1992 on July 24, 2010, 06:34:02 am

hmm I studied wikipedia's explanation yesterday and altough I do not quite understand everything I think this:

let d be so that d times e = 1 times mod(_psi_(pq))
couldn't that be:
d=mod(_psi_(pq)) divided by e

forgive me if this is either obvious or stupid, I do math on intuition most of the times :P

Here is a list of most of the required variables (these are the onse I understand):

P = prime (uniformly random to q)
q = prime (uniformly random to p)
Bitlenght P = Bitlenght q
n = p times q
_psi_(n) = (p-1) times (q-1)
e = random(2.....up to x?)

What is the upperbound of e? is it p-1?
once again my apologies if I am asking silly questions again...

Title: Re: New RSA Algorithm discussion
Post by: Lionel Debroux on July 24, 2010, 07:53:35 am

e is fixed, 17 for the 512-bit RSA keys of TI-Z80 and TI-68k calcs and 65537 for the 1024-bit RSA keys of Nspire calcs.

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on July 24, 2010, 09:38:44 am

Matthias, you are mistaken when you say it is one times mod. Also, that's not an equal to symbol but a congruence. (wikipedia) basically, it means de-1 mod t=<equals>0, where t=<equals>(p-1)(q-1). In other words, de-1 is evenly divisible by t. Also look up modular multiplicative inverse on wikipedia.

Title: Re: New RSA Algorithm discussion
Post by: matthias1992 on July 24, 2010, 10:05:15 am

Aah ok. my bad. I indeed had mistaken it for a = sign but i didn't notice the extra bar underneath it, it was far past midnight if that is a righteous excuse :P

And on modular arithmetic, I am trying to learn that now, I never had it on school. Maybe the kahnacademy (on youtube) hosts it?

on a off-topic note, the kahnacademy on youtube is a great resource for math you never had or never understood, I can recommend it to everyone. Just hit kahnacademy on YT.

Thanks for the explanation graphmastur.

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on July 24, 2010, 12:20:46 pm

No problem. This thread's other purpose, besides finding a new way to break RSA keys, is to explain how it works. To explain modular arithmetic, it is basically this.

If you have 21 mod 5, that is the remainder of 21 divided by 5, or 1. If you have 21 mod 4, that also equals 1 because the remainder of 21 divided by 4 equals 1.

Now 221 is congruent to 1 mod 55, because (221-1) mod 55=0.

Does that make sense?

Title: Re: New RSA Algorithm discussion
Post by: matthias1992 on July 24, 2010, 12:55:40 pm

yes it does, thank you.

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on July 26, 2010, 09:05:56 pm

Glad it does. So, any ideas for an algorithm? I'm working on one using a reduced row echelon form of a matrix with the last column being each digit of the number.

Also, are there any recursive or cyclical algorithms for factoring a number? If so, I would be interested in seeing them. (Note: I do not mean like a simple for loop, or go until a condition is met.)

Title: Re: New RSA Algorithm discussion
Post by: bwang on July 26, 2010, 09:13:34 pm

Here's a very simple "cyclical" algorithm: http://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
I do not know of any recursive algorithms.
In case anyone is interested, I'll attach my Java QS implementation. It implements the sieving step from the QS, and is utterly useless (because Java is inherently slow) except for educational purposes. It builds the matrix, but I haven't implemented block Lanczos yet.

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on July 27, 2010, 03:07:49 pm

Oh, thanks for that. It will help. Also, I never understood what the pollard rho algorithm meant by "pseudo-random function modulo n". I understand modulo n, but what about the pseudo random part?

Title: Re: New RSA Algorithm discussion
Post by: fb39ca4 on July 27, 2010, 03:25:09 pm

I don't really understand the Pollard-Rho algorithm either, but I think it was meant for numbers with lots of small factors.

Title: Re: New RSA Algorithm discussion
Post by: Lionel Debroux on July 27, 2010, 03:31:50 pm

Indeed, the Pollard Rho heuristic works well for small factors.

Title: Re: New RSA Algorithm discussion
Post by: bwang on July 27, 2010, 04:24:41 pm

The "pseudo-random function" is usually simply f(x) = x^2 + 1 mod n. It means that the sequence f(x), f(f(x)), f(f(f(x))), ... behaves like a random sequence.

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on July 27, 2010, 05:05:50 pm

I see. So basically, it randomly tries to find the factor with a slightly better success rate than just random numbers.

Title: Re: New RSA Algorithm discussion
Post by: ExtendeD on July 28, 2010, 06:03:55 am

Quote from: fb39ca4 on July 21, 2010, 12:12:12 pm

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

I've only skimmed through the topic, but the answer posted doesn't seem to be correct. The boot2 and OS signatures are checked at each boot.

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on July 28, 2010, 08:08:06 am

Well, even so, if you crack the rsa key, then it wouldn't make any difference.

Title: Re: New RSA Algorithm discussion
Post by: Eeems on July 28, 2010, 07:36:07 pm

I was just thinking, is there any way to create a custom OS receiver and then force the calc to run that OS? so like disable to old OS and use the new one, so then any edits to the new OS that you make will be saved.

Title: Re: New RSA Algorithm discussion
Post by: apcalc on July 28, 2010, 07:39:12 pm

Quote from: Eeems on July 28, 2010, 07:36:07 pm

I was just thinking, is there any way to create a custom OS receiver and then force the calc to run that OS? so like disable to old OS and use the new one, so then any edits to the new OS that you make will be saved.

Well, there is runos, which might do just that, but I am not exactly sure how runos works. Nevertheless, I doubt that runos will be released.

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on July 28, 2010, 07:53:35 pm

Kinda off-topic, btw.

Anyway, I'm busy, but I'm still working on an algorithm. Do y'all have any observations on the relationship between semiprimes and their two prime factors?

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on August 03, 2010, 04:50:32 pm

If we were to solve this diophantine equation, we would easily have the roots of n:
xy+x(x-1)=n
x²+xy-x=n
with y=0, it is simply the square root of n+x.
y=1 always gives the square root of n.
y=2 always gives the square root of n-x.
y=3 always gives the square root of

Now then, assume that f(x)=x²+xy-x=n. Let us try n=221 first. It's factors are p=13 and q=17, where pq=221=n. Now, f(p)=n and f(q)=n. In f(x), there is a y variable. With f(p), y=(q-p+1), and with f(q), y=(p-q+1) So the question is, how to solve it as a diophantine equation.

Anyone have any experience with diophantine equations? (Please don't post links to wikipedia)

Title: Re: New RSA Algorithm discussion
Post by: willrandship on September 08, 2010, 09:17:56 pm

Hey, is there any way to take the various OS versions and compare their hashes to find the key?

We have access to about 9 (i think) Os versions, so there's lots of hashes to compare. Even small portions of the key would be extremely valuable.

Title: Re: New RSA Algorithm discussion
Post by: qazz42 on September 08, 2010, 09:40:22 pm

http://www.engadget.com/2010/03/09/1024-bit-rsa-encryption-cracked-by-carefully-starving-cpu-of-ele/

was this mentioned yet? ^ ^

Title: Re: New RSA Algorithm discussion
Post by: calcdude84se on September 08, 2010, 09:43:47 pm

yes, but it isn't applicable :(
The Nspire's have the public key, but we need the private key, which is what TI has and won't give to us :P

Title: Re: New RSA Algorithm discussion
Post by: qazz42 on September 08, 2010, 09:46:31 pm

oh, sry then, my bad..

Title: Re: New RSA Algorithm discussion
Post by: willrandship on September 08, 2010, 09:55:39 pm

yeah, we don't need to starve the CPU for that key. We already have it from rom dumps.

Question: does anyone know how much the OS code actually changes from version to version? If it's not much, just stuff added on to the existing code (def. not from 1.7 to 2.0, but maybe from 1.4 to 1.6 or 2.0 to 2.1?)

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on September 09, 2010, 06:01:30 pm

We can't use the hashes to find the private key. I believe, that this is because of how a signature works. Anyway, I'm gonna go look up how they sign it. I think it's just encryption of the MD5 hash, with the private key, and that might allow some Chinese remainder magic, but I don't know. We would have to know how the hashes are made in the first place. EG, over what data is the hash made.

Anyway, I still think that the best way to do it is to factor the numbers.

Title: Re: New RSA Algorithm discussion
Post by: Snake X on October 02, 2010, 10:08:34 pm

hey.. so about rsa keys, how would I encrypt something myself? I use openssl right? I got ubuntu on vmware player so i can use any ubuntu app if i need to..

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on October 02, 2010, 10:17:08 pm

If you have oppenssl, then this page can help here (http://www.devco.net/archives/2006/02/13/public_-_private_key_encryption_using_openssl.php)

If you have any more questions, feel free to ask.

Title: Re: New RSA Algorithm discussion
Post by: kyllopardiun on October 16, 2010, 02:17:59 pm

What about distributed computing?

I mean like rainbow crack...
it could not be very fast, but the concept of softwares like seti@home
can do a lot of things in some amount of time that you won't be able to do alone.

Think, with the help of let me say 50 users using something to factor just a part of it and then sending the progress back for continue the work.

With all these, we won't get the RSA keys quickly, but possibly in a 4 month work it will be able for everyone.

Title: Re: New RSA Algorithm discussion
Post by: Lionel Debroux on October 17, 2010, 05:40:33 am

We've already had lots of talk about factoring the key, in another topic (but it's understandable that you missed it: there's lots of activity on the forum, and that is a good thing): http://ourl.ca/6236 :)

I have summarized multiple times how impractical the factorization is (unless some ground-breaking algorithm comes to the rescue, which we should not hold our breath on): basically, three orders of magnitude harder than the state of the art.
A linear extrapolation of the figures given in the paper detailing the factorization of RSA-768, consistent with what we know of 512-bit RSA factoring, gives the need of sifting through 10000-100000 TB (yes, I really mean terabytes) of data, after those have been produced by several dozen thousands of computers running for years (or ten times as many computers, running for one tenth of the time).
This does not, however, mean that we can't spend up to several CPU-years trying to find a factor by Trial Factoring (beyond that would not be reasonable): it's extremely unlikely that we'll succeed by sifting through a search space which represents an vanishingly small part of a particle, compared to the whole universe - but such is the beauty of random.

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on October 17, 2010, 08:07:16 am

Which is the reason this topic is here. To explain rsa and find a new algorithm.

Title: Re: New RSA Algorithm discussion
Post by: Lionel Debroux on October 17, 2010, 09:40:26 am

No argument there ;)
I was just explaining him that distributed computing probably wouldn't help enough for the factorization to become practical, with the current algorithms :)

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on October 17, 2010, 09:52:14 am

With current algorithms, it would require so much Time and computational power that it wouldn't be feasible. That is why I like recursive algorithms that run in log n time. ;-)

Title: Re: New RSA Algorithm discussion
Post by: kyllopardiun on October 17, 2010, 11:14:27 am

sorry for not have seen the other topic before...

Quote from: Lionel Debroux on October 17, 2010, 09:40:26 am

No argument there ;)
I was just explaining him that distributed computing probably wouldn't help enough for the factorization to become practical, with the current algorithms :)

Actually, rainbow crack //I don't know how much you know about it, but isn't for RSA keys, my suggestion was something like it, not it, maybe I should say it more explicit...
And I said it because I like to divide in tables for giving each one a part to do, as I like also the style of these tables.
But, it can't be used as it is for factoring a RSA key.

=/

Quote from: graphmastur on October 17, 2010, 09:52:14 am

With current algorithms, it would require so much Time and computational power that it wouldn't be feasible. That is why I like recursive algorithms that run in log n time. ;-)

Are you sure that isn't any recursive algorithm?
That's sad after so many time none came yet.

but, sometimes when using some recursive functions in c I see that computer many times will do much more quickly than a n function, but, it will crash before the end.

//I tried this, exactly with a friend to see which program in c was faster, both used pointers, but mine had a little more of it and was recursive.
mine was pretty quickly at start and then crashed at some number. while his took sometime to achieve that number, but
after it done it continued to next numbers.

Title: Re: New RSA Algorithm discussion
Post by: fb39ca4 on October 17, 2010, 12:09:51 pm

I thought the rainbow crack was for windows passwords...

Title: Re: New RSA Algorithm discussion
Post by: kyllopardiun on October 17, 2010, 12:18:36 pm

Quote from: fb39ca4 on October 17, 2010, 12:09:51 pm

I thought the rainbow crack was for windows passwords...

It was made for crack MD5, then they started to include other keys like LM, NTLM, SHA1, MYSQLSHA1, HALFLMCHALL, NTLMCHALL, ORACLE-SYSTEM, MD5-HALF

but, nothing for RSA yet.
And it run in both linux and Ruindows <- (inside joke) just can speak portuguese will understand...

Title: Re: New RSA Algorithm discussion
Post by: DJ Omnimaga on October 18, 2010, 12:32:03 am

Lol never heard the Ruindows thing before, but in English it almost fits the OS perfectly ;D. People usually just say Winblows, Window$ and French people say Windaube. :P

Title: Re: New RSA Algorithm discussion
Post by: kyllopardiun on October 18, 2010, 06:52:21 am

Quote from: DJ Omnimaga on October 18, 2010, 12:32:03 am

Lol never heard the Ruindows thing before, but in English it almost fits the OS perfectly ;D. People usually just say Winblows, Window$ and French people say Windaube. :P

Ruim in portuguese: bad/poor,
but now, I thought about it and you are right. I think it does fit better in english than in portuguese..
:D

Title: Re: New RSA Algorithm discussion
Post by: DJ Omnimaga on October 18, 2010, 01:23:47 pm

Ah I see ;D

Of course it's possible to ruin your data with Linux too if you totally do something wrong but I think it is less common. I don't hear often about Linux crashes forcing a reformatting.

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on October 18, 2010, 01:36:36 pm

true. but there a lot less linux users too. So, hasvanyone thought about rsa much?

Title: Re: New RSA Algorithm discussion
Post by: kyllopardiun on October 18, 2010, 08:34:19 pm

Quote from: graphmastur on October 18, 2010, 01:36:36 pm

true. but there a lot less linux users too. So, hasvanyone thought about rsa much?

Since my table ideas wasn't good, there's just another thing in my mind that sounds plausible to get the RSA keys,
and it's 5.9
however, I don't think we should go that far...

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on October 18, 2010, 10:07:00 pm

5.9? And what do you mean we shouldn't go that far?

Also, no idea is a bad idea really. It's just that some will work with small scale numbers while some don't.

Title: Re: New RSA Algorithm discussion
Post by: kyllopardiun on October 18, 2010, 10:13:48 pm

Quote from: graphmastur on October 18, 2010, 10:07:00 pm

5.9? And what do you mean we shouldn't go that far?
Also, no idea is a bad idea really. It's just that some will work with small scale numbers while some don't.

If you knew what 5.9 is probably you would agree ...

5.9 is a way,( btw one of the best of them) to exploit the critical point on everything done yet.
and it depends, it can work very well [usually do] or you won't get anything at all.

5.9 it's a way of SEing. If you know what this is will help a lot for you understand.

//for some reasons I don't feel comfortable to explain much better what it really is neither how does it work here, in a open topic.

Title: Re: New RSA Algorithm discussion
Post by: mapar007 on October 19, 2010, 03:40:29 am

Quote from: DJ Omnimaga on October 18, 2010, 12:32:03 am

Lol never heard the Ruindows thing before, but in English it almost fits the OS perfectly ;D. People usually just say Winblows, Window$ and French people say Windaube. :P

We usually say Windhoos (=cyclone) or something. There's also this: (Rutt'n ahtenehenteh in West-Vlaams. Hilarious.)

(Note: this is not how ALL Flemish people talk)

On a more on-topic note: Rainbowcrack was not made for our purpose, because we're talking about a key that is far longer than the average password, and storing the tables for reuse is pointless in this setting (that's the No. 1 reason why you would use RC).

I'm sure you will agree with us after having read: en.wikipedia.org/wiki/RSA . This algorithm is invulnerable. Cryptanalysts have done all they could. Thinking that a bunch of youngsters with calcs can break a 1024-bit key, let alone find a flaw in the algorithm, is VERY utopic.

Title: Re: New RSA Algorithm discussion
Post by: fb39ca4 on October 19, 2010, 03:44:48 pm

Lets save up some money so we can buy a quantum computer once they come out.

Title: Re: New RSA Algorithm discussion
Post by: kyllopardiun on November 30, 2010, 05:00:05 am

Would help, if we had all the factorials stored in a file?

I am saying this because I saw, this (http://www.wolframalpha.com/input/?i=10000!) and found it pretty amazing.

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on November 30, 2010, 06:16:16 am

Quote from: kyllopardiun on November 30, 2010, 05:00:05 am

Would help, if we had all the factorials stored in a file?

I am saying this because I saw, this (http://www.wolframalpha.com/input/?i=10000!) and found it pretty amazing.

Not really. Yeah it would help in some ways, but not completely. For one thing, you would have to find an algorithm to find the factors based on the factorial in case you had both or none of the factors in the factorial. eg. the factors would cancel out in the factorial. Also, for the amount of time it would take, and all the numbers you would have to go through, it would be easier to simply go through each number to the the sqrt(n) and try to find the factor that way. Then there's the disk space involved...

Title: Re: New RSA Algorithm discussion
Post by: SirCmpwn on February 27, 2011, 04:17:10 pm

I think there may be a simple method we have overlooked. This isn't neccissarily the best resource, but this (http://primes.utm.edu/primes/lists/all.txt) is a list of the top 500 known prime numbers. Perhaps we can multiply them to each other until we find n? I know it's brute force, but hey, it could work.

Title: Re: New RSA Algorithm discussion
Post by: ruler501 on February 27, 2011, 04:21:57 pm

Could you generate a range reducing the numbers that have to be searched. Aren't the two numbers supposed to be pretty close in bit size? We could then use an optimized algorithm that would just have to go through a much smaller amount of numbers.

If wahat I said is stupid I'm sorry I know almost nothing about this.

Title: Re: New RSA Algorithm discussion
Post by: fb39ca4 on February 27, 2011, 04:41:37 pm

Quote from: SirCmpwn on February 27, 2011, 04:17:10 pm

I think there may be a simple method we have overlooked. This isn't neccissarily the best resource, but this (http://primes.utm.edu/primes/lists/all.txt) is a list of the top 500 known prime numbers. Perhaps we can multiply them to each other until we find n? I know it's brute force, but hey, it could work.

Th prime numbers used in the key are around 2^512. The ones in that list are much, much larger. Even if we found all the primes near 2^512, we would have a lot of work to do because by the prime number theorem, there is about 2^503 of them.

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on February 27, 2011, 04:52:19 pm

Quote from: SirCmpwn on February 27, 2011, 04:17:10 pm

I think there may be a simple method we have overlooked. This isn't neccissarily the best resource, but this (http://primes.utm.edu/primes/lists/all.txt) is a list of the top 500 known prime numbers. Perhaps we can multiply them to each other until we find n? I know it's brute force, but hey, it could work.

Quite possibly, but unlikely. It would work if it only had one factor, but if it has both, it won't work. The best thing dealing with that I've seen, is start off with some prime number S₁. Then, multiply 1 S₁ with 2 S₂. S₂ is the next prime lower than S₁. This would take huge initial amounts of memory and would output the file that had this number for some bound B. So, for example:
B=11
S₁=11
S₂=7
S₃=5
S₄=3
S₅=2
11*(7*7)*(5*5*5)*(3*3*3*3)*(2*2*2*2*2)= 174636000

So, for numbers like 35, we get:
174636000 mod 35 = 0, so we do 174636000 / 35 = 4,989,600.
4989600 mod 35 = 0, so we do 4989600 / 35 =142,560
142,560 mod 35 = 5, hey look a factor.

It gets slightly strange on numbers like 33. (Pretty much any number that doesn't have it's other prime next to it. I'm just going to use // to mean divide it out as far as it will go out completely. e.g., no fraction or decimal points after dividing.
174,636,000 // 33 =5,292,000
5,292,000 mod 33 = 21. Strange I know, but you only have to do gcd(21,33) to get 3, which is a factor.

So the problem involves setting your maximum bound, and figuring out how many times each number should be multiplied, and sending that task out to whatever... hmmm... Me has an idea. I could figure that out, by just saying the maximum bound B minus whatever prime number you are on S, plus 1. So say the upper bound is 11 (B), and we need to know how many times to multiply 5 in. So 11-5+1=7. So that adds slight redundancy but it's easier to split on many machines.

I couldl set up a site that allows you to download data file(s), and a program (Most likely java for easy portability), and gives rewards based on how many you have completed. Simply download the file, run the program, upload the output, and you get a point or something. Sounds good to me! What do you think?

Title: Re: New RSA Algorithm discussion
Post by: SirCmpwn on February 27, 2011, 04:53:50 pm

Go for it. I just started my own program as well, and I encourage others to do the same. Let's get this damn thing done.

Title: Re: New RSA Algorithm discussion
Post by: ruler501 on February 27, 2011, 05:00:11 pm

I agree. I hope we can get the range we need lowered down. 2^503 is better than 2^512. I think we could narrow it down using simple algorithms couldn't we? does anyone know where a list of primes around 5^12 are? We just need everything from 2^511 to 2^513 shouldn't we. then an algorithm that sorts through those for likely matches. after that another algorithm to sort for the one match we need.

Title: Re: New RSA Algorithm discussion
Post by: AngelFish on February 27, 2011, 05:12:09 pm

Here's a paper from the most successful RSA factorization thus far:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.156.9709&rep=rep1&type=pdf (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.156.9709&rep=rep1&type=pdf)

Also, graph, your method appears to try to find the prime factorization of the keys. The fact of the matter is that the prime factors in question are 1024 bits long. That means that you're essentially brute forcing the problem. It wouldn't really reduce the complexity of the problem.

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on February 27, 2011, 05:17:18 pm

Quote from: Qwerty.55 on February 27, 2011, 05:12:09 pm

Also, graph, your method appears to try to find the prime factorization of the keys. The fact of the matter is that the prime factors in question are 1024 bits long. That means that you're essentially brute forcing the problem. It wouldn't really reduce the complexity of the problem.

That's incorrect, actually, I only need to find factors that are 512 bits for a 1024 bit key. And the cool part is that the more people contribute, the better chances we get to having it work. Also, with this, we can use the same number to factor any other keys, or increase the bound. (Although by increasing that, you would have to say larger numbers get more factors. So, essentially, we should make the bound around 2^768, and start around the 512 bit area. The only reason it sounds remotely reasonable, is because we can just check when someone submits something if it has it in there, or just store it otherwise for other numbers. Sounds good enough to me to at least try it.

EDIT: Also, to you non-basic programmers, let the no ending parenthesis just bug you. :devil:

Title: Re: New RSA Algorithm discussion
Post by: ruler501 on February 27, 2011, 05:23:37 pm

Must... add... ending... parentheses...
;)

Title: Re: New RSA Algorithm discussion
Post by: SirCmpwn on February 27, 2011, 05:26:50 pm

What is the maximum 512-bit prime number? Does anyone know?
(If not, the biggest non-prime 512-bit number works, too)
Also, what is a reasonably good distance between numbers to try?

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on February 27, 2011, 05:33:26 pm

Quote from: SirCmpwn on February 27, 2011, 05:26:50 pm

What is the maximum 512-bit prime number? Does anyone know?
(If not, the biggest non-prime 512-bit number works, too)
Also, what is a reasonably good distance between numbers to try?

The reasonable distance is essentially random. Smallest number bellow 2^512? That would be slightly difficult. Just start at 2^512, I guess.

Title: Re: New RSA Algorithm discussion
Post by: AngelFish on February 27, 2011, 05:34:35 pm

The upper bound on the gap between two Prime numbers of the required size is approximately ln(2^513)

Title: Re: New RSA Algorithm discussion
Post by: SirCmpwn on February 27, 2011, 05:35:06 pm

The numbers should be close to each other, it says. So how close is close?

Title: Re: New RSA Algorithm discussion
Post by: AngelFish on February 27, 2011, 05:35:35 pm

Sir, see my post above yours ;)

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on February 27, 2011, 05:36:40 pm

Somewhere between two and ln(2^513)

Title: Re: New RSA Algorithm discussion
Post by: SirCmpwn on February 27, 2011, 05:36:47 pm

Could I have that number in hex? :)
Nevermind, it's about 356.

Title: Re: New RSA Algorithm discussion
Post by: Xeda112358 on February 27, 2011, 05:36:52 pm

They could be adjacent odd numbers so that means the number could be N(N+2), right?

Title: Re: New RSA Algorithm discussion
Post by: AngelFish on February 27, 2011, 05:37:40 pm

Yes. The lower bound on the gap is 2. However, there are numerous primes that are not part of the set of twin primes.

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on February 27, 2011, 05:38:05 pm

Quote from: SirCmpwn on February 27, 2011, 05:36:47 pm

Could I have that number in hex? :)

somewhere between 0x2 and 0x164

Title: Re: New RSA Algorithm discussion
Post by: AngelFish on February 27, 2011, 05:42:07 pm

Or somewhere between 0x2 and 0x200 ;)

ln_2(0x1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000)=0x200

Title: Re: New RSA Algorithm discussion
Post by: SirCmpwn on February 27, 2011, 05:49:57 pm

This code should find the key, right?
I'm adding some other housekeeping things, but this is the actual key finding code:

Code: [Select]

static void Main(string[] args)
        {
            // Boot2 Key:
            // c3b3a7015c04299ff3a25f104e2285c1ec2d55471e6208959d0f6981b2fa2c6d
            // 3e316f9364d5eb5c7789e142b75bfaf402e7e02fac0cb09f6419db1f44679f8b
            // bcca142f1d312feb095708ef175a4ef80271321e7240f0d854c90a74fc59209c
            // df80aa8f85ae3b948a3ce55c69cd050098d5a79aebbc241cc642b106b1af2cb7

            // Other keys:
            // aba7f0b8c7feb6e33438af5c25c67389eaf4d73f80cd0a37922493431cde03b3
            // 4da448bdb05387cf7a8c59ee12d9613429a2b07ea385752f079892da1ae76c2b
            // 158f2d7169aae066432fe44f797df39dd6a0d7b2e2091281b30efac247c51576
            // ebc93ec456de2e27d36b713844336b65af67ee58e6107a6a1deb954a91095295

            // b15e01c47c421be62f4e769b3ac98f4f983a820b0c181e35715d84a4f1acf052
            // 7eeddfabf9f66e73bedb55376e22f860c34dc70ce239157297056d4ecf465357
            // 78c3917647b5a6bb9c5638cdeff3e309ff66878fd4f233cf157d7af4136f307d
            // f90ec6ae6eaff6bead6d52f423a37dac59ff38ae876008103728f2bd674e858f

            Console.WriteLine("Factoring 1024-bit TI-Nspire boot2 RSA Key:");
            Console.WriteLine("0xc3b3a7015c04299ff3a25f104e2285c1ec2d55471e6208959d0f6981b2fa2c6d");
            Console.WriteLine("0x3e316f9364d5eb5c7789e142b75bfaf402e7e02fac0cb09f6419db1f44679f8b");
            Console.WriteLine("0xbcca142f1d312feb095708ef175a4ef80271321e7240f0d854c90a74fc59209c");
            Console.WriteLine("0xdf80aa8f85ae3b948a3ce55c69cd050098d5a79aebbc241cc642b106b1af2cb7");

            BigInteger key = new BigInteger("c3b3a7015c04299ff3a25f104e2285c1ec2d55471e6208959d0f6981b2fa2c6d" +
                "3e316f9364d5eb5c7789e142b75bfaf402e7e02fac0cb09f6419db1f44679f8b" +
                "bcca142f1d312feb095708ef175a4ef80271321e7240f0d854c90a74fc59209c" +
                "df80aa8f85ae3b948a3ce55c69cd050098d5a79aebbc241cc642b106b1af2cb7", 16);

            BigInteger startValue = new BigInteger("1552518092300708935148979488462502555256886017116696611139052038026050952686376886330878408828646477950487730697131073206171580044114814391444287275041181139204454976020849905550265285631598444825262999193716468750892846853816057856", 10);
            string maxNumber = "";
            while (maxNumber.Length * 8 < 512)
                maxNumber += "F";
            BigInteger maxValue = new BigInteger(maxNumber, 8);

            Console.Write("\n");

            BigInteger numberOne = startValue, numberTwo = startValue + 2;
            BigInteger numberOfTests = 0;
            BigInteger temp = 0;
            BigInteger distance = 356;


            while (true)
            {
                Console.Clear();
                numberOfTests++;
                Console.WriteLine("Number of tests thus far: {0}\n", numberOfTests.ToString());
                Console.WriteLine("Current numbers:");
                Console.WriteLine(numberOne.ToHexString() + "\n");
                Console.WriteLine(numberTwo.ToHexString());
                if (numberOne * numberTwo == key)
                {
                    Console.WriteLine("----Key found----");
                    while (true)
                        Console.ReadLine(); // Stop here
                }
                Console.WriteLine("Current test done, searching for next prime pair...");
                while (true)
                {
                    numberOne++;
                    if ((numberOne - numberTwo).abs() > 356)
                    {
                        numberTwo++;
                        while (!numberTwo.isProbablePrime())
                            numberTwo++;
                        numberOne = numberTwo + 2;
                        while (!numberOne.isProbablePrime())
                            numberTwo++;
                        break;
                    }
                    if (numberOne.isProbablePrime())
                        break;
                }
            }
        }

Title: Re: New RSA Algorithm discussion
Post by: willrandship on February 27, 2011, 05:50:10 pm

another quick thing;

if you check division by all the primes up to a certain point, you know the factor is inside of this (k=key, p=highest prime checked) from k/P to sqrt(k)

This becomes less and less effective the higher you go, unfortunately, because of shrinking square roots. however, with a little twisting of the algorithm you can eliminate it in the other direction instead. Note: this looks for the higher factor, whereas the perl script looks for the lower factor (ie 3*11=33, this would find 11 and they would find 3, irrelevant in implementation, but good to know)

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on February 27, 2011, 05:52:06 pm

Code: [Select]

BigInteger maxValue = new BigInteger(maxNumber, 8);

should be 16 instead of 8, correct?

Title: Re: New RSA Algorithm discussion
Post by: SirCmpwn on February 27, 2011, 05:52:43 pm

Already fixed.
I also think that the code that finds the next pair to test isn't working, any ideas?

Title: Re: New RSA Algorithm discussion
Post by: willrandship on February 27, 2011, 05:56:06 pm

right, but you count up with this method. Really, this would serve best as a range finder, for where to start something else.

@sir, remember to start on an odd number. ;)

Title: Re: New RSA Algorithm discussion
Post by: alberthrocks on February 27, 2011, 05:58:49 pm

I'm loving this! :D (Especially the Folding@Home kind of idea! ;))
Just before we go too crazy, some things I'd like to suggest:

1) Server submission - should be written in PHP or some web language. It must withstand many submissions (a mini DDoS, practically :P), and it has to be stable. The client prgm, after submitting, should pull the latest batch of numbers for backup. The server also reports any mirrors (mirrors are a MUST - you don't want numbers lost!), and the server reports if it's the main server or not. It can also report a main/mirror change if needed. If a factor is found, the main server should email everyone the key immediately, and proceed to pastebin the key as well. My server can act as the mirror, but it may need donations to get it at a good state. It won't be a main server tho – 512 MB of RAM is pretty shabby... :P

2) Client – I'd like to keep it up and running 24/7, but I don't want to have to stop it every time. An idea is to have it probe CPU usage. If it sees high CPU usage, it'll stop. Once the CPU usage goes down, it'll wait for a buffer 2-3 minutes before resuming work. Work, as usual, should be saved as much as possible. That way, it can act like a service/daemon/background program. :)

Indication of the client's activity can be achieved with wxWidgets via tray icon. (And if possible, a notification)

Also, as said above, it should submit their number, and pull an update list and such.

That's all! :) Continue discussing numbers! :P

EDIT: for CPU usage probing, probe every 10 seconds. Don't probe continuously or every second - then you'll be taking 100% CPU... :P

Title: Re: New RSA Algorithm discussion
Post by: SirCmpwn on February 27, 2011, 06:01:34 pm

So it looks like my program works, I need to add some more stuff and it shall be glorious. It's pretty slow though, averaging about 30 tests a minute. This is because it only tests numbers that are likely to be prime, and it takes time to find the next psuedoprime number. I'll add some stuff to reduce redundancy when others use it simultaneously, and persistance between runs, as well as crash protection (you shouldn't have to start over just because something went wrong.

Title: Re: New RSA Algorithm discussion
Post by: willrandship on February 27, 2011, 06:02:11 pm

One major issue is duplication. We only need to check each num once, so I think a server that held the ranges alreay checked would be nice. It would only take ~1024 bits per range, and big ranges would be the same size stored as small ranges :)

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on February 27, 2011, 06:03:48 pm

@alberthro yeah, you pretty much described boinc there. :D

Title: Re: New RSA Algorithm discussion
Post by: broooom on February 27, 2011, 06:04:21 pm

I can do the server-side software. :)

Title: Re: New RSA Algorithm discussion
Post by: SirCmpwn on February 27, 2011, 06:04:45 pm

Quote from: willrandship on February 27, 2011, 06:02:11 pm

One major issue is duplication.

Quote from: SirCmpwn on February 27, 2011, 06:01:34 pm

...I'll add some stuff to reduce redundancy when others use it simultaneously...

Title: Re: New RSA Algorithm discussion
Post by: willrandship on February 27, 2011, 06:13:07 pm

and how does that work? sounds cool but it also sounds like you'll need a server, and net access on all the pcs running it.

Maybe we could just config the prog to run a specified range, and claim them on here....

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on February 27, 2011, 06:13:40 pm

Quote from: willrandship on February 27, 2011, 06:13:07 pm

and how does that work? sounds cool but it also sounds like you'll need a server, and net access on all the pcs running it.

Maybe we could just config the prog to run a specified range, and claim them on here....

Well, that's essentially what the site I was/am going to set up will do.

Title: Re: New RSA Algorithm discussion
Post by: SirCmpwn on February 27, 2011, 06:13:52 pm

No, it doesn't need a server, and runs on almost every platform imaginable. You'll be able to specify your range, and claim it here.

Title: Re: New RSA Algorithm discussion
Post by: willrandship on February 27, 2011, 06:26:03 pm

Sweet! if only we could recover all the work we wasted on the perl script :P

@sir does that include z80 asm?

Title: Re: New RSA Algorithm discussion
Post by: SirCmpwn on February 27, 2011, 06:27:53 pm

Every platform that it would be reasonable to run a key factoring program on.

Title: Re: New RSA Algorithm discussion
Post by: willrandship on February 27, 2011, 06:30:08 pm

Ok :P
is it java then? or perhaps C?

Title: Re: New RSA Algorithm discussion
Post by: z80man on February 27, 2011, 06:30:49 pm

Quote from: SirCmpwn on February 27, 2011, 06:27:53 pm

Every platform that it would be reasonable to run a key factoring program on.

Maybe z80 isn't reasonable enough, but SH3 could add just that little oomph of speed needed to factor the RSA.

And Java is not fast enough.

Title: Re: New RSA Algorithm discussion
Post by: SirCmpwn on February 27, 2011, 06:30:58 pm

It's C#, and under Mono it can run pretty much anywhere.

Title: Re: New RSA Algorithm discussion
Post by: alberthrocks on February 27, 2011, 06:36:23 pm

A server is being set up atm, with broooom coding the thing since I don't have time atm to do it. :(
A server is OPTIONAL - the program can surely work fine without it. :) It is just there to store values and such.

Title: Re: New RSA Algorithm discussion
Post by: willrandship on February 27, 2011, 06:36:32 pm

eh, bytecode is slow, be it java, C# or python .pyc files. It has it's place, but IMO this is a place for machine code.

Title: Re: New RSA Algorithm discussion
Post by: alberthrocks on February 27, 2011, 06:39:14 pm

I think the current plan is to get a good base working, API and all (client and server communications), then we can start porting it to C/C++. :) I'd definitely like to see wxWidgets come into this (although I hate C++, it does have good stuff in it).

Cross platform is key - the .NET based one won't be discarded - it'll still be used for other devices.
The C/C++ one will be used for mainly PCs and such that can run it.

Title: Re: New RSA Algorithm discussion
Post by: SirCmpwn on February 27, 2011, 06:40:54 pm

Quote from: alberthrocks on February 27, 2011, 06:39:14 pm

Cross platform is key - the .NET based one won't be discarded - it'll still be used for other devices.

.NET is more cross-platform than anything else you can think of. And its the only technology that we could feasibly make such a complex program with.

Title: Re: New RSA Algorithm discussion
Post by: alberthrocks on February 27, 2011, 06:43:44 pm

Quote from: SirCmpwn on February 27, 2011, 06:40:54 pm

Quote from: alberthrocks on February 27, 2011, 06:39:14 pm
Cross platform is key - the .NET based one won't be discarded - it'll still be used for other devices.
.NET is more cross-platform than anything else you can think of. And its the only technology that we could feasibly make such a complex program with.

.NET is not the only technology that you can make complex programs with.... :P
C/C++ has been used (Lionel's program to do this, for instance)...

Title: Re: New RSA Algorithm discussion
Post by: SirCmpwn on February 27, 2011, 06:44:39 pm

I'll make one with .NET, and you can choose whether or not to use it. I hope for the community's sake that people use it if there isn't an alternitave they'd prefer.

Title: Re: New RSA Algorithm discussion
Post by: calc84maniac on February 27, 2011, 08:23:35 pm

Here's a checking algorithm that tests based on the difference between the two primes.

Let N=p1*p2 be the number to factor, and let p1=A-B, and p2=A+B for integers A and B. p1 and p2 differ by 2B (a valid assumption for two large prime numbers). Then N=(A-B)(A+B)=A^2-B^2. Thus, N+B^2=A^2.

Here's some pseudocode (N=number to factor, B=initial value of B):

Code: [Select]

x=N+B*B;
dx=2*B+1;
A=floor(sqrt(x));
y=A*A;
dy=2*A+1;
while(x != y)
{
  y += dy;
  dy += 2;
  while(x < y)
  {
    x += dx;
    dx += 2;
  }
}
A = (dy-1)/2;
B = (dx-1)/2;
p1 = A-B;
p2 = A+B;

This is simple enough that it might be possible to write an optimized assembly version. That would be awesome :D

Title: Re: New RSA Algorithm discussion
Post by: alberthrocks on February 27, 2011, 08:51:20 pm

Quote from: SirCmpwn on February 27, 2011, 06:44:39 pm

I'll make one with .NET, and you can choose whether or not to use it. I hope for the community's sake that people use it if there isn't an alternitave they'd prefer.

People will, no worries. Remember, the key is portability, ease of use, and speed. (Ease of use as in a very primitive but easy GUI, and that icon I've mentioned about.) The program has to stay out of the way of the user - otherwise, it's kinda tricky to keep on without having 2+ cores... :P

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on February 27, 2011, 09:34:43 pm

@calc84maniac. That's not a bad algorithm at all. In fact, if you could solve the Diophantine equation N=A²-B², we could solve it pretty quickly. That's one of the main things I've been using to try and break this. (Besides tree structures, and bit error checking)

Title: Re: New RSA Algorithm discussion
Post by: z80man on February 27, 2011, 09:37:33 pm

If we did factor the nspire RSA key, would that be the largest key ever factored before in history?

Title: Re: New RSA Algorithm discussion
Post by: AngelFish on February 27, 2011, 09:38:00 pm

Yes.

Title: Re: New RSA Algorithm discussion
Post by: z80man on February 27, 2011, 09:39:04 pm

Then could we be in the Guinness book of world records ::)

Title: Re: New RSA Algorithm discussion
Post by: willrandship on February 27, 2011, 09:39:17 pm

I've been mainly focusing on ways to reduce the ways you check the numbers, without storing anything and without cpmlicated algorithms. IMO, you're better off using multiple PCs to check the same range than making one PC do a fancy equation, adding load.

so far my most productive has been column elimination.

Title: Re: New RSA Algorithm discussion
Post by: AngelFish on February 27, 2011, 09:40:31 pm

Just to put everything in perspective, this problem is around 1.1579*10^77 times as difficult as the most difficult keys ever factored.

Title: Re: New RSA Algorithm discussion
Post by: willrandship on February 27, 2011, 09:41:10 pm

yeah, we've heard all that :P

Title: Re: New RSA Algorithm discussion
Post by: calc84maniac on February 27, 2011, 09:41:30 pm

I also thought of a way to optimize the loop (especially lending itself to assembly programming where you can use the carry flag):

Code: [Select]

x=B*B;
db=2*B-1;
A=floor(sqrt(N+x));
x-=(A*A-N);
da=2*A-1;
while(x)
{
  x -= (da += 2);
  do
    x += (db += 2);
  while(no_carry);
}
A = (da+1)/2;
B = (db+1)/2;
p1 = A-B;
p2 = A+B;

Title: Re: New RSA Algorithm discussion
Post by: AngelFish on February 27, 2011, 09:41:42 pm

All the more reason to crack it :P

Title: Re: New RSA Algorithm discussion
Post by: willrandship on February 27, 2011, 09:45:16 pm

Mine can be implemented in any other algorithm, but it lends itself to a different tracking style.

Title: Re: New RSA Algorithm discussion
Post by: ruler501 on February 27, 2011, 11:35:04 pm

I think this might be possible if we can narrow the range enough. Do we currently have a program to do that? I believe that that is the key to breaking the key(plus effective FAST algorithms). I wish you all the best of luck and I will help if I can.

Would this be in violation of the DMCA by any chance?

Title: Re: New RSA Algorithm discussion
Post by: AngelFish on February 27, 2011, 11:39:29 pm

It shouldn't be. Anything involved with the DMCA is legally fuzzy though. We really need to get a decent and clear law to replace that grey mess of a document.

Title: Re: New RSA Algorithm discussion
Post by: ruler501 on February 27, 2011, 11:42:12 pm

Well aren't we working to break through protection that prevents stealing of copyrighted materials(CAS OS to Non-CAS) I thought that was illegal under the DMCA. I agree though we do need a new one.
I think we need to get this more focused on a way to break RSA not a way to break the Nspires RSA.(at least hats what we'll say) So that make sit seem less illegal...

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on February 28, 2011, 12:51:39 am

It's not illegal either way. I wouldn't mess with it if it was. You will get slapped with a DMCA notice, but after breaking a 1024 bit key, it would be impossible to even take them all down, besides being monetarily infeasable.

Now, since we can view the code anyway, and since iPhone jailbreaking is now legal, then so is this. Besides, distribution of numbers is not illegal, nor is seining them to slashdot, hackaday, and pretty much every other site known to man. Expect 500+ guests if they link to omni.

This should be fun.

Title: Re: New RSA Algorithm discussion
Post by: DJ Omnimaga on February 28, 2011, 01:09:48 am

Quote from: SirCmpwn on February 27, 2011, 06:13:52 pm

No, it doesn't need a server, and runs on almost every platform imaginable. You'll be able to specify your range, and claim it here.

Ah I see what the range was for then. I was wondering how we would avoid duplicates while doing our own thing alone on each side x.x.

I wonder how many years this will take, though...

Title: Re: New RSA Algorithm discussion
Post by: Builderboy on February 28, 2011, 01:11:29 am

Quote from: graphmastur on February 28, 2011, 12:51:39 am

Expect 500+ guests if they link to omni.

This should be fun.

I'm gonna say don't count your chickens before they hatch :P So the basic mentality here is that, we know its unlikely, but we are going for it against all odds? I'm in :)

Title: Re: New RSA Algorithm discussion
Post by: AngelFish on February 28, 2011, 01:11:31 am

Best case: It'll be solved by tomorrow.

Worst case: The sun will have died by the time the solution is found using this method.

Title: Re: New RSA Algorithm discussion
Post by: DJ Omnimaga on February 28, 2011, 02:40:04 am

I think Slashdot and the like mostly post about stuff that has been done, not planned to be done, so it might not work. But otherwise I am not sure of a good way to convince other people to get into the project. It would take thousands and thousands of them, and then there would be a need for a server so we don't have to put like 1000 people in the first post.

Title: Re: New RSA Algorithm discussion
Post by: Lionel Debroux on February 28, 2011, 08:08:58 am

Quoting myself from reply #71 in this very topic:

Quote

We've already had lots of talk about factoring the key, in another topic (but it's understandable that you missed it: there's lots of activity on the forum, and that is a good thing): http://ourl.ca/6236 :)

I have summarized multiple times how impractical the factorization is (unless some ground-breaking algorithm comes to the rescue, which we should not hold our breath on): basically, three orders of magnitude harder than the state of the art.
A linear extrapolation of the figures given in the paper detailing the factorization of RSA-768, consistent with what we know of 512-bit RSA factoring, gives the need of sifting through 10000-100000 TB (yes, I really mean terabytes) of data, after those have been produced by several dozen thousands of computers running for years (or ten times as many computers, running for one tenth of the time).
This does not, however, mean that we can't spend up to several CPU-years trying to find a factor by Trial Factoring (beyond that would not be reasonable): it's extremely unlikely that we'll succeed by sifting through a search space which represents an vanishingly small part of a particle, compared to the whole universe - but such is the beauty of random.

Title: Re: New RSA Algorithm discussion
Post by: fb39ca4 on February 28, 2011, 04:11:21 pm

Quote from: Qwerty.55 on February 28, 2011, 01:11:31 am

Best case: It'll be solved by tomorrow.

Worst case: The sun will have died by the time the solution is found using this method.

By the time the sun dies out, I'm pretty sure we'll have quantum computers.

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on February 28, 2011, 05:26:02 pm

We all know complexity of it. I know it very well in fact. We're actually pretty much hoping to get lucky here. ;-)

Title: Re: New RSA Algorithm discussion
Post by: SirCmpwn on February 28, 2011, 05:38:53 pm

I think we need to move away from the arguments about the infeasibility of this and move on to making it happen.

Title: Re: New RSA Algorithm discussion
Post by: DJ Omnimaga on February 28, 2011, 06:14:15 pm

Yeah to be fair I agree with Sir. Of course later it might be best to move on to more powerful computers and have this run on multiple computers from multiple people, because it's gonna take a friggin long while, but the thing is that in 2004-07, people said a Gameboy emulator for the 84+ was impossible, same for a Mode 7 engine, yet people managed to do it a few years later. Trying stuff is what makes the community progress. Not trying anything because we expect it to not work at all gives a 2008 POTY in long terms.

Title: Re: New RSA Algorithm discussion
Post by: willrandship on February 28, 2011, 06:22:01 pm

Yay for that.

Title: Re: New RSA Algorithm discussion
Post by: Tribal on March 07, 2011, 05:34:00 pm

I've been trying to find some function that could be used to find the next number that *might* be a factor in a semiprime. I've been using this program to get my test data, I can't really explain what it's doing so if someone with more math skill than me and can understand this program, if you would I would appreciate it ;)

Code: [Select]

:PQ→N:1→F
:int(√(N→X
:{0→L1:L1→L2
:For(θ,1,2
:While (fPart(N/X)>fPart(N/(X+1)))+(θ=2
:If X=Q-1:Return
:X-1→X:F+1→F
:If θ=2:Then
:If X>0:Then
:If fPart(N/X)<fPart(N/(X+1:Then
:Disp {X,F
:If L1(1)=0
:Then
:{X→L1
:{F→L2
:Else
:X→L1(dim(L1)+1
:F→L2(dim(L2)+1
:End
:X-1→X:1→F
:End
:End
:End
:End
:X-1→X
:End

(not very effective because of the limited memory on the calculator, have to find almost a perfect semiprime to work with. Might try whipping up a C program that can be used to get/graph the data)

EDIT: Right now this program assumes Q is the smaller of the two primes. Just add '(P>Q)Q+(Q>P)P→L' at the beginning and change 'If X=Q-1:Return' to 'If X=L-1:Return'.

Title: Re: New RSA Algorithm discussion
Post by: willrandship on March 07, 2011, 05:48:02 pm

theoretically, we don't have to find a way to solve all semiprimes, just one :P
hmmmm

Title: Re: New RSA Algorithm discussion
Post by: DJ Omnimaga on March 07, 2011, 11:46:15 pm

Quote from: Tribal on March 07, 2011, 05:34:00 pm

I've been trying to find some function that could be used to find the next number that *might* be a factor in a semiprime. I've been using this program to get my test data, I can't really explain what it's doing so if someone with more math skill than me and can understand this program, if you would I would appreciate it ;)

Code: [Select]
:PQ→N:1→F :int(√(N→X :{0→L1:L1→L2 :For(θ,1,2 :While (fPart(N/X)>fPart(N/(X+1)))+(θ=2 :If X=Q-1:Return :X-1→X:F+1→F :If θ=2:Then :If X>0:Then :If fPart(N/X)<fPart(N/(X+1:Then :Disp {X,F :If L1(1)=0 :Then :{X→L1 :{F→L2 :Else :X→L1(dim(L1)+1 :F→L2(dim(L2)+1 :End :X-1→X:1→F :End :End :End :End :X-1→X :End
(not very effective because of the limited memory on the calculator, have to find almost a perfect semiprime to work with. Might try whipping up a C program that can be used to get/graph the data)

EDIT: Right now this program assumes Q is the smaller of the two primes. Just add '(P>Q)Q+(Q>P)P→L' at the beginning and change 'If X=Q-1:Return' to 'If X=L-1:Return'.

Do you want to factor the TI-Nspire key from a TI calc using TI-BASIC? O.O

j/k interesting. :P

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on March 08, 2011, 07:04:08 am

Quote from: Tribal on March 07, 2011, 05:34:00 pm

EDIT: Right now this program assumes Q is the smaller of the two primes. Just add '(P>Q)Q+(Q>P)P→L' at the beginning and change 'If X=Q-1:Return' to 'If X=L-1:Return'.

usually P is used as the smaller. And if you already know P or Q, why do we need to find it?

Title: Re: New RSA Algorithm discussion
Post by: Tribal on March 08, 2011, 10:12:36 am

Quote from: graphmastur on March 08, 2011, 07:04:08 am

Quote from: Tribal on March 07, 2011, 05:34:00 pm
EDIT: Right now this program assumes Q is the smaller of the two primes. Just add '(P>Q)Q+(Q>P)P→L' at the beginning and change 'If X=Q-1:Return' to 'If X=L-1:Return'.
usually P is used as the smaller. And if you already know P or Q, why do we need to find it?

I was randomly throwing a prime in P and Q, so I didn't know which was smaller.
In these scenarios I am using a known P and Q only to generate a semiprime N. From that, I'm trying to find a formula that would give the amount of numbers away from what might be the factor of N(I'm not actually using P or Q for anything except to get N and to stop after I've reached the lower of the two). With this function, it may speed up any TF'ing because you are not checking every other number, you would be checking the number given by the function. I believe that the function is uniform to all semiprimes as well, because the graph given for a random semiprime is equivalent if not the same for all of them. I'm not exactly sure how to find this function though, that's where I'm stuck at. It is a exponential graph that has multiple asymptotes, but from that I don't know what todo :/

Title: Re: New RSA Algorithm discussion
Post by: Tribal on July 15, 2011, 02:29:36 am

***NECRODOUBLEPOST***

It's been awhile since I did anything with this because of so many factors, but I decided to write my tibasic code into C so I could use bigger primes. I made a flowchart (http://i.imgur.com/ojm1J.png) to help me figure out what exactly is going on since I haven't touched this in awhile, and for anybody who didn't really know it was that it was doing in the first place. I'm still pursuing this because I have a strong feeling I was onto something, and it would be a great discovery.

Also, maybe this topic should be moved under the 'Math and Science' subforums?

Title: Re: New RSA Algorithm discussion
Post by: calcdude84se on July 15, 2011, 05:52:47 am

Done. It'd be cool if something useful actually came out of this. We could use a great discovery, and it'd make all Nspire users happy. :D

Title: Re: New RSA Algorithm discussion
Post by: ruler501 on July 15, 2011, 08:50:04 am

Quote from: Tribal on July 15, 2011, 02:29:36 am

***NECRODOUBLEPOST***

It's been awhile since I did anything with this because of so many factors, but I decided to write my tibasic code into C so I could use bigger primes. I made a flowchart (http://i.imgur.com/UB68M.jpg) to help me figure out what exactly is going on since I haven't touched this in awhile, and for anybody who didn't really know it was that it was doing in the first place. I'm still pursuing this because I have a strong feeling I was onto something, and it would be a great discovery.

Also, maybe this topic should be moved under the 'Math and Science' subforums?

could you explain what the program is doing? The flow chart confused me...
I'd like to help if I could. Good luck at finding something

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on July 15, 2011, 11:09:41 am

You really should mark yes and no on your flow chart. Also, I don't know what ISQRT(p,q) is to know what X is. I also don't know what you assume for P and Q. Also, there are some nodes that have 3 outputs, too.

Title: Re: New RSA Algorithm discussion
Post by: Tribal on July 15, 2011, 04:02:53 pm

Quote from: graphmastur on July 15, 2011, 11:09:41 am

You really should mark yes and no on your flow chart. Also, I don't know what ISQRT(p,q) is to know what X is. I also don't know what you assume for P and Q. Also, there are some nodes that have 3 outputs, too.

Sorry, I put 'False' on the false routes, so if it isn't false assume true. I also fixed some mistakes and added a notes thing at the top. Also, ISQRT is just integer sqrt, which can be thought of as the floored result of sqrt. It's also less confusing with all the mistakes gone <_>

Updated flowchart: hhttp://i.imgur.com/ojm1J.png (http://i.imgur.com/ojm1J.png)

Title: Re: New RSA Algorithm discussion
Post by: fb39ca4 on July 15, 2011, 04:11:39 pm

But how can ISQRT have two inputs?

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on July 15, 2011, 04:12:59 pm

Quote from: t0xic_kitt3n on July 15, 2011, 04:11:39 pm

But how can ISQRT have two inputs?

That's what I'm trying to figure out. I think it's finding the square root of N, actually.

Title: Re: New RSA Algorithm discussion
Post by: Tribal on July 15, 2011, 04:27:03 pm

Spoiler For IGNORE:

EDIT: AGH! I'm just not thinking straight x.x
Yeah, it should be finding the sqrt of n like graphmastur said. Updated all flowchart links with the corrected version.

EDIT2: More flowchart errors addressed and all links (re)updated again.
EDIT3: I factored out some of the complexity of the former flowchart, here is the new one: http://i.imgur.com/sSkWK.png (http://i.imgur.com/sSkWK.png)
EDIT4: One last error: The starting value of F should be 0 not 1 for the new flowchart. I'm to lazy to upload another flowchart atm, so just so y'all know.
EDIT5: I got the C++ version done, source code is below.

Code: [Select]

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <vector>

#define FPART(x) (float)(((float)x)-floor((float)x))

inline unsigned int isqrt(unsigned int n) {
    unsigned int i;
    for (i = 0; n >= (2*i)+1; n -= (2*i++)+1);
    return i;
}

int main(int argc, char *argv[]) {
    FILE *fp;
    unsigned int f, p, q, n, x, l;
    std::vector<unsigned int> xy;
    
    f = 1;
    p = atoi(argv[1]);
    q = atoi(argv[2]);
    n = p * q;
    x = isqrt(n);
    l = (p > q) ? q : p;

    for(; FPART(n/x) > FPART(n/(x+1)); --x);

    for(; x > l-1; ++f, --x) {
        if (FPART(n/x) > FPART(n/(x+1)))
            continue;
        xy.push_back(x);
        xy.push_back(f);
        f = 0;
    }
    
    fp = fopen("dataset", "w");
    fprintf(fp, "%u %u %zu ", p, q, xy.size());
    for (x = 0; x < xy.size(); ++x)
        fprintf(fp, "%u ", xy[x]);

    fprintf(fp, "\n");
    fclose(fp);

    return EXIT_SUCCESS;
}

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on July 16, 2011, 10:47:54 pm

Okay, and have you tested how well it works?

Title: Re: New RSA Algorithm discussion
Post by: Tribal on July 17, 2011, 04:38:50 am

I'm not quite sure what you expect by 'working' but... As far as I know it outputs exactly what the TI-BASIC version would, except in a slightly different way. It outputs everything to dataset, the first three numbers indicate the two primes entered, the third represents how much data there is. After that it is just x, y coordinates one after another. And of course it can handle larger numbers and is faster at what it does. I'm still not exactly sure how to make a function from this data, I'll work more on that later. The main reasons for making the C++ version was for the speed and to check and see if the pattern that I saw on the calculator's graph extended beyond numbers I couldn't test.

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on July 17, 2011, 10:27:48 pm

By working, I mean, not only does it do what you expected, but that it can in fact help factor them faster, and won't skip the factor accidentally.

Title: Re: New RSA Algorithm discussion
Post by: Tribal on July 18, 2011, 01:36:26 am

The program isn't really meant to *factor* anything. It gets test data from doing a the comparison 'fpart(n/x) < fpart (n/(x+1))' where n is a semiprime and x is the current number counting down from sqrt(n). If the condition is true, the number between the last successful comparison and the current comparison is stored as the y coordinate and the current 'x' is stored as the x coordinate. For any semiprime numbers, this gives a graph that is always similar to http://i.imgur.com/lZKUX.png (http://i.imgur.com/lZKUX.png).

EDIT: That's kind of an old screenshot, but iirc that graph checks all numbers to zero instead of stopping at the factor. I did this on purpose to see what the results were. The C++ version would only show the last of the three asymptotes.

Title: Re: New RSA Algorithm discussion
Post by: AngelFish on July 18, 2011, 03:10:32 am

Can we close this topic until someone comes up with a practical crack of the RSA algorithm itself? I don't mean to be a downer, but here's the situation:

Given the current 2048 bit keys and classical computations, the scale of the problem is vastly more difficult than even the largest keys broken today (768 bits). By vast, I mean volume of the known universe measured in nanometers vast*. The chance that anyone will solve it is so exceedingly slim that the only mathematical tool I have available to calculate it has to work with arbitrary precision operations simply in order to present it. Unless someone gets their hands on a massive quantum computer running Shor's algorithm**, it is, in short, an impossible problem. Feel free to prove me wrong, but the community's CPU cycles could be better spent on other projects.

*Even this is an understatement.

**It'd take about 30 seconds for a quantum computer to break the code, since the computations necessary increase according to (lg n)^3 for an n bit key.

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on July 18, 2011, 01:31:31 pm

That's why this topic exists. Don't close this topic at all.

Title: Re: New RSA Algorithm discussion
Post by: Xeda112358 on July 18, 2011, 02:49:41 pm

I have not read anything from previous posts, but I would just like to say that I still want to prove useful to this topic someday. I have been absorbing myself in mathematics-- particularly in number theory and prime numbers-- and I have filled up several notebooks since my vacation started. I have not found a way to factor in polynomial time, yet, but I believe that there is a way to factor specifically double prime numbers in polynomial time. I have made a way to deterministically (did I spell that correctly) test if a number is prime or composite and I am working on developing several new syntaxes for doing math that will help with these kinds of problems. One of these works on making new number systems with a slight modification to the definition of a prime number. For example, I have number sets where every single number is prime in that set, even though not all of them are prime in the set of natural numbers. If I can get anywhere with those number systems, I hope to apply the results to the natural numbers.

So for ideas, what if you defined a number to be prime so long as it is relatively prime to every number in the set? For example, {5,6,10,11} would have the primes as 5,6, and 11. If you work with a series such as {2,3,7,43,1+43*42...} every number is then "prime" to that set. Anywho, I hope I wasn't totally and completely off topic. I only had a few minutes to post before I get booted off the interwebs so I didn't read beyond the topic title.

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on July 18, 2011, 11:04:10 pm

That's fine, indeed. Please let us know if that turns up anything interesting. I don't fully understand how it's prime in one number set, and not in the other, but okay.

Title: Re: New RSA Algorithm discussion
Post by: calc84maniac on July 18, 2011, 11:08:09 pm

Quote from: Xeda112358 on July 18, 2011, 02:49:41 pm

So for ideas, what if you defined a number to be prime so long as it is relatively prime to every number in the set?

Over the set of natural numbers, by that definition only 1 is prime. Pick any other number, and you can find another number that is not relatively prime to it (for example, the number times 2)

Title: Re: New RSA Algorithm discussion
Post by: AngelFish on July 18, 2011, 11:10:40 pm

Actually, all of the normal primes would be prime according to that definition, since no other number evenly divides them. I'm not sure where Xeda's going with that, though, since integer factorization is only NP-complete if the numbers are prime relative to the set of natural numbers.

Title: Re: New RSA Algorithm discussion
Post by: Xeda112358 on July 19, 2011, 03:34:02 pm

I was only going with the idea that if I could find any relations there with the double prime numbers in those sets, they may be able to be applied to the set of natural numbers. On a different note, a triangle that I have been working on has been yielding some very nice patterns (by triangle, I mean things like Pascals Triangle). Interestingly enough, setting it up as a square and eliminating the first row and column as well as the diagonal, most of the numbers are appearing to be prime and all of the values can be easily computed. I had not designed the triangle specifically for this purpose, but it would be nice if there was a predictable pattern in it. If there is, I have furthered that interpolation stuff I was working on before to handle multiple variables, so I could easily make the equation. I will try to describe the triangle though if anybody is interested.
-The first diagonal going from the top number to the left to infinity is modeled by X²
-The diagonal going right is modeled by -X²
-These diagonals can be called P₀ and Z₀, respectively.
-The second diagonals are P₁ and Z₁
-The diagonals are labeled as P_s and Z_r
-P_s(r)=Z_r(n)=r²+rs-s²

I think I may have switched that last rule around, but the first few terms look like:
0 1 -1 4 1 -4 9 5 -1 -9
The triangle was originally formed through other means, but after finding this pattern, this is how I am defining it for the moment. I do not have much more time, but if anybody wants to have fun, you can try to find how the Fibonacci and Lucas sequence tie into this 3:-)

Title: Re: New RSA Algorithm discussion
Post by: Tribal on July 21, 2011, 08:17:01 pm

An update on the way I've been approaching this issue, storing the frequency as the x-coordinate instead of the number it's currently on seems to fit a logistic curve quite nicely. The curve seems to fit pretty well with basically any primes as well, it's just the height of the curve that seems to be variable.

Title: Re: New RSA Algorithm discussion
Post by: Xeda112358 on August 12, 2011, 06:49:31 pm

My computer is about to die and my charger is broken. Anyway, I am onto something that might let me give y'all an equation that produces all the primes in the form of 2ⁿ+1. Would that help in any way? Also, I cannot make any guarantees about this, it is just a hunch.

Spoiler For Spoiler:

If I am right, this is a prime number (assuming my calculations are correct):
2003529930406846464979072351560255750447825475569751419265016973710894059556311453089506130880933348101038234342907263181822949382118812668869506364761547029165041871916351587966347219442930927982084309104855990570159318959639524863372367203002916969592156108764948889254090805911457037675208500206671563702366126359747144807111774815880914135742720967190151836282560618091458852699826141425030123391108273603843767876449043205960379124490905707560314035076162562476031863793126484703743782954975613770981604614413308692118102485959152380195331030292162800160568670105651646750568038741529463842244845292537361442533614373729088303794601274724958414864915930647252015155693922628180691650796381064132275307267143998158508811292628901134237782705567421080070065283963322155077831214288551675554073345107213112427399562982719769150054883905223804357045848197956393157853510018992000024141963706813559840464039472194016069517690156119726982337890017641517190051133466306898140219383481435426387306539552969691388024158161859561100640362119796101859534802787167200122604642492385111393400464351623867567078745259464670903886547743483217897012764455529409092021959585751622973333576159552394885297579954028471943529913543763705986928913757153740001986394332464890052543106629669165243419174691389632476560289415199775477703138064781342309596190960654591300890188887588084733625956065444888501447335706058817090162108499714529568344061979690565469813631162053579369791403236328496233046421066136200220175787851857409162050489711781820400187282939943446186224328009837323764931814789848119452713007440220765680910376203999203492023906626264491909167985461515778839060397720759279378852241294301017458086862263369284725851403039615558564330385450688652213114813638408384778263790459607186876728509763471271988890680478243230394718650525660978150729861141430305816927924971409161059417185352275887504477592218301158780701975535722241400019548102005661773589781499532325208589753463547007786690406429016763808161740550405117670093673202804549339027992491867306539931640720492238474815280619166900933805732120816350707634351669869625020969023162859350071874190579161241536897514808261904847946571736601005892476655445840838334790544144817684255327207315586349347605137419779525190365032198020108764738368682531025183377533908861426184800374008082238104076468878471647552945326947661700424461063311238021134588694532200116564076327023074292426051582811070387018345324567635625951430032037432740780879056283663406965030844225855967039271869461158513793386475699748568670079823960604393478850861649260304945061743412365828352144806726676841807083754862211408236579802961200027441324438432402331257403545019352428776430880232850855886089962774458164680857875115807014743763867976955049991643998284357290415378143438847303484261903388841494031366139854257635577105335580206622185577060082551288893332226436281984838613239570676191409638533832374343758830859233722284644287996245605476932428998432652677378373173288063210753211238680604674708428051166488709084770291208161104912555598322366244868556651402684641209694982590565519216188104341226838996283071654868525536914850299539675503954938371853405900096187489473992880432496373165753803673586710175783994818471798498246948060532081996066183434012476096639519778021441199752546704080608499344178256285092726523709898651539462193004607364507926212975917698293892367015170992091531567814439791248475706237804600009918293321306880570046591458387208088016887445835557926258465124763087148566313528934166117490617526671492672176128330845273936469244582892571388877839056300482483799839692029222215486145902373478222682521639957440801727144146179559226175083889020074169926238300282286249284182671243405751424188569994272331606998712986882771820617214453142574944015066139463169197629181506579745526236191224848063890033669074365989226349564114665503062965960199720636202603521917776740668777463549375318899587866282125469797102065747232721372918144666659421872003474508942830911535189271114287108376159222380276605327823351661555149369375778466670145717971901227117812780450240026384758788339396817962950690798817121690686929538248529830023476068454114178139110648560236549754227497231007615131870024053910510913817843721791422528587432098524957878034683703337818421444017138688124249984418618129271198533315382567321870421530631197748535214670955334626336610864667332292409879849256691109516143618601548909740241913509623043612196128165950518666022030715613684732364660868905014263913906515063908199378852318365059897299125404479443425166774299659811849233151555272883274028352688442408752811283289980625912673699546247341543333500147231430612750390307397135252069338173843322950701049061867539433130784798015655130384758155685236218010419650255596181934986315913233036096461905990236112681196023441843363334594927631946101716652913823717182394299216272538461776065694542297877071383198817036964588689811863210976900355735884624464835706291453052757101278872027965364479724025405448132748391794128826423835171949197209797145936887537198729130831738033911016128547415377377715951728084111627597186384924222802373441925469991983672192131287035585307966942713416391033882754318613643490100943197409047331014476299861725424423355612237435715825933382804986243892498222780715951762757847109475119033482241412025182688713728193104253478196128440176479531505057110722974314569915223451643121848657575786528197564843508958384722923534559464521215831657751471298708225909292655638836651120681943836904116252668710044560243704200663709001941185557160472044643696932850060046928140507119069261393993902735534545567470314903886022024639948260501762431969305640666366626090207048887438898907498152865444381862917382901051820869936382661868303915273264581286782806601337500096593364625146091723180312930347877421234679118454791311109897794648216922505629399956793483801699157439700537542134485874586856047286751065423341893839099110586465595113646061055156838541217459801807133163612573079611168343863767667307354583494789788316330129240800836356825939157113130978030516441716682518346573675934198084958947940983292500086389778563494693212473426103062713745077286156922596628573857905533240641849018451328284632709269753830867308409142247659474439973348130810986399417379789657010687026734161967196591599588537834822988270125605842365589539690306474965584147981310997157542043256395776070485100881578291408250777738559790129129407309462785944505859412273194812753225152324801503466519048228961406646890305102510916237770448486230229488966711380555607956620732449373374027836767300203011615227008921843515652121379215748206859356920790214502277133099987729459596952817044582181956080965811702798062669891205061560742325686842271306295009864421853470810407128917646906550836129916694778023822502789667843489199409657361704586786242554006942516693979292624714524945408858422726153755260071904336329196375777502176005195800693847635789586878489536872122898557806826518192703632099480155874455575175312736471421295536494084385586615208012115079075068553344489258693283859653013272046970694571546959353658571788894862333292465202735853188533370948455403336565356988172582528918056635488363743793348411845580168331827676834646291995605513470039147876808640322629616641560667508153710646723108461964247537490553744805318226002710216400980584497526023035640038083472053149941172965736785066421400842696497103241919182121213206939769143923368374709228267738708132236680086924703491586840991153098315412063566123187504305467536983230827966457417620806593177265685841681837966106144963432544111706941700222657817358351259821080769101961052229263879745049019254311900620561906577452416191913187533984049343976823310298465893318373015809592522829206820862230332585280119266496314441316442773003237792274712330696417149945532261035475145631290668854345426869788447742981777493710117614651624183616680254815296335308490849943006763654806102940094693750609845588558043970485914449584445079978497045583550685408745163316464118083123079704389849190506587586425810738422420591191941674182490452700288263983057950057341711487031187142834184499153456702915280104485145176055306971441761368582384102787659324662689978418319620312262421177391477208004883578333569204533935953254564897028558589735505751235129536540502842081022785248776603574246366673148680279486052445782673626230852978265057114624846595914210278122788941448163994973881884622768244851622051817076722169863265701654316919742651230041757329904473537672536845792754365412826553581858046840069367718605020070547247548400805530424951854495267247261347318174742180078574693465447136036975884118029408039616746946288540679172138601225419503819704538417268006398820656328792839582708510919958839448297775647152026132871089526163417707151642899487953564854553553148754978134009964854498635824847690590033116961303766127923464323129706628411307427046202032013368350385425360313636763575212604707425311209233402837482949453104727418969287275572027615272268283376741393425652653283068469997597097750005560889932685025049212884068274139881631540456490350775871680074055685724021758685439053228133770707415830756269628316955687424060527726485853050611356384851965918968649596335568216975437621430778665934730450164822432964891270709898076676625671517269062058815549666382573829274182082278960684488222983394816670984039024283514306813767253460126007269262969468672750794346190439996618979611928750519442356402644303271737341591281496056168353988188569484045342311424613559925272330064881627466723523751234311893442118885085079358163848994487544756331689213869675574302737953785262542329024881047181939037220666894702204258836895840939998453560948869946833852579675161882159410981624918741813364726965123980677561947912557957446471427868624053750576104204267149366084980238274680575982591331006919941904651906531171908926077949119217946407355129633864523035673345588033313197080365457184791550432654899559705862888286866606618021882248602144999973122164138170653480175510438406624412822803616648904257377640956326482825258407669045608439490325290526337532316509087681336614242398309530806549661879381949120033919489494065132398816642080088395554942237096734840072642705701165089075196155370186264797456381187856175457113400473810762763014953309735174180655479112660938034311378532532883533352024934365979129341284854970946826329075830193072665337782559314331110963848053940859283988907796210479847919686876539987477095912788727475874439806779824968278272200926449944559380414608770641941810440758269805688038949654616587983904660587645341810289907194293021774519976104495043196841503455514044820928933378657363052830619990077748726922998608279053171691876578860908941817057993404890218441559791092676862796597583952483926734883634745651687016166240642424241228961118010615682342539392180052483454723779219911228595914191877491793823340010078128326506710281781396029120914720100947878752551263372884222353869490067927664511634758101193875319657242121476038284774774571704578610417385747911301908583877890152334343013005282797038580359815182929600305682612091950943737325454171056383887047528950563961029843641360935641632589408137981511693338619797339821670761004607980096016024823096943043806956620123213650140549586250615282588033022908385812478469315720323233601899469437647726721879376826431828382603564520699468630216048874528424363593558622333506235945002890558581611275341783750455936126130852640828051213873177490200249552738734585956405160830583053770732533971552620444705429573538361113677523169972740292941674204423248113875075631319078272188864053374694213842169928862940479635305150560788126366206497231257579019598873041195626227343728900516561111094111745277965482790471250581999077498063821559376885546498822938985408291325129076478386322494781016753491693489288104203015610283386143827378160946341335383578340765314321417150655877547820252454780657301342277470616744241968952613164274104695474621483756288299771804186785084546965619150908695874251184435837306590951460980451247409411373899927822492983367796011015387096129749705566301637307202750734759922943792393824427421186158236161317886392553095117188421298508307238259729144142251579403883011359083331651858234967221259621812507058113759495525022747274674369887131926670769299199084467161228738858457584622726573330753735572823951616964175198675012681745429323738294143824814377139861906716657572945807804820559511881687188075212971832636442155336787751274766940790117057509819575084563565217389544179875074523854455200133572033332379895074393905312918212255259833790909463630202185353848854825062897715616963860712382771725621313460549401770413581731931763370136332252819127547191443450920711848838366818174263342949611870091503049165339464763717766439120798347494627397822171502090670190302469762151278521956142070806461631373236517853976292092025500288962012970141379640038055734949269073535145961208674796547733692958773628635660143767964038430796864138563447801328261284589184898528048048844180821639423974014362903481665458114454366460032490618763039502356402044530748210241366895196644221339200757479128683805175150634662569391937740283512075666260829890491877287833852178522792045771846965855278790447562192663992008409302075673925363735628390829817577902153202106409617373283598494066652141198183810884515459772895164572131897797907491941013148368544639616904607030107596818933741217575988165127000761262789169510406315857637534787420070222051070891257612361658026806815858499852631465878086616800733264676830206391697203064894405628195406190685242003053463156621891327309069687353181641094514288036605995220248248886711554429104721929134248346438705368508648749099178812670565665387191049721820042371492740164460943459845392536706132210616533085662021188968234005752675486101476993688738209584552211571923479686888160853631615862880150395949418529489227074410828207169303387818084936204018255222271010985653444817207470756019245915599431072949578197878590578940052540122867517142511184356437184053563024181225473266093302710397968091064939272722683035410467632591355279683837705019855234621222858410557119921731717969804339317707750755627056047831779844447637560254637033369247114220815519973691371975163241302748712199863404548248524570118553342675264715978310731245663429805221455494156252724028915333354349341217862037007260315279870771872491234494477147909520734761385425485311552773301030342476835865496093722324007154518129732692081058424090557725645803681462234493189708138897143299831347617799679712453782310703739151473878692119187566700319321281896803322696594459286210607438827416919465162267632540665070881071030394178860564893769816734159025925194611823642945652669372203155504700213598846292758012527715422016629954863130324912311029627923723899766416803497141226527931907636326136814145516376656559839788489381733082668779901962886932296597379951931621187215455287394170243669885593888793316744533363119541518404088283815193421234122820030950313341050704760159987985472529190665222479319715440331794836837373220821885773341623856441380700541913530245943913502554531886454796252260251762928374330465102361057583514550739443339610216229675461415781127197001738611494279501411253280621254775810512972088465263158094806633687670147310733540717710876615935856814098212967730759197382973441445256688770855324570888958320993823432102718224114763732791357568615421252849657903335093152776925505845644010552192644505312073756287744998163646332835816140330175813967359427327690448920361880386754955751806890058532927201493923500525845146706982628548257883267398735220457228239290207144822219885587102896991935873074277815159757620764023951243860202032596596250212578349957710085626386118233813318509014686577064010676278617583772772895892746039403930337271873850536912957126715066896688493880885142943609962012966759079225082275313812849851526902931700263136328942095797577959327635531162066753488651317323872438748063513314512644889967589828812925480076425186586490241111127301357197181381602583178506932244007998656635371544088454866393181708395735780799059730839094881804060935959190907473960904410150516321749681412100765719177483767355751000733616922386537429079457803200042337452807566153042929014495780629634138383551783599764708851349004856973697965238695845994595592090709058956891451141412684505462117945026611750166928260250950770778211950432617383223562437601776799362796099368975191394965033358507155418436456852616674243688920371037495328425927131610537834980740739158633817967658425258036737206469351248652238481341663808061505704829059890696451936440018597120425723007316410009916987524260377362177763430621616744884930810929901009517974541564251204822086714586849255132444266777127863728211331536224301091824391243380214046242223349153559516890816288487989988273630445372432174280215755777967021666317047969728172483392841015642274507271779269399929740308072770395013581545142494049026536105825409373114653104943382484379718606937214444600826798002471229489405761853892203425608302697052876621377373594394224114707074072902725461307358541745691419446487624357682397065703184168467540733466346293673983620004041400714054277632480132742202685393698869787607009590048684650626771363070979821006557285101306601010780633743344773073478653881742681230743766066643312775356466578603715192922768440458273283243808212841218776132042460464900801054731426749260826922155637405486241717031027919996942645620955619816454547662045022411449404749349832206807191352767986747813458203859570413466177937228534940031631599544093684089572533438702986717829770373332806801764639502090023941931499115009105276821119510999063166150311585582835582607179410052528583611369961303442790173811787412061288182062023263849861515656451230047792967563618345768105043341769543067538041113928553792529241347339481050532025708728186307291158911335942014761872664291564036371927602306283840650425441742335464549987055318726887926424102147363698625463747159744354943443899730051742525110877357886390946812096673428152585919924857640488055071329814299359911463239919113959926752576359007446572810191805841807342227734721397723218231771716916400108826112549093361186780575722391018186168549108500885272274374212086524852372456248697662245384819298671129452945515497030585919307198497105414181636968976131126744027009648667545934567059936995464500558921628047976365686133316563907395703272034389175415267500915011198856872708848195531676931681272892143031376818016445477367518353497857924276463354162433601125960252109501612264110346083465648235597934274056868849224458745493776752120324703803035491157544831295275891939893680876327685438769557694881422844311998595700727521393176837831770339130423060958999137314684569010422095161967070506420256733873446115655276175992727151877660010238944760539789516945708802728736225121076224091810066700883474737605156285533943565843756271241244457651663064085939507947550920463932245202535463634444791755661725962187199279186575490857852950012840229035061514937310107009446151011613712423761426722541732055959202782129325725947146417224977321316381845326555279604270541871496236585252458648933254145062642337885651464670604298564781968461593663288954299780722542264790400616019751975007460545150060291806638271497016110987951336633771378434416194053121445291855180136575558667615019373029691932076120009255065081583275508499340768797252369987023567931026804136745718956641431852679054717169962990363015545645090044802789055701968328313630718997699153166679208958768572290600915472919636381673596673959975710326015571920237348580521128117458610065152598883843114511894880552129145775699146577530041384717124577965048175856395072895337539755822087777506072339445587895905719156737

Title: Re: New RSA Algorithm discussion
Post by: Goplat on August 12, 2011, 08:51:41 pm

Numbers of the form 2^2ⁿ + 1 are called Fermat numbers. Yours is F16 and is already known to be divisible by 825753601 and 188981757975021318420037633 (http://www.prothsearch.net/fermat.html).

Title: Re: New RSA Algorithm discussion
Post by: AngelFish on August 12, 2011, 09:05:03 pm

Well, Ninja'd.

Title: Re: New RSA Algorithm discussion
Post by: fb39ca4 on August 13, 2011, 12:17:09 am

Xeda, you're not the only one that has tried that. I had thought about that when I was ten, and I thought I had discovered something huge :P.

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on August 15, 2011, 03:52:12 pm

Indeed, unfortunately, nothing new here. I have no new ideas about this right now either, unfortunately.

Title: Re: New RSA Algorithm discussion
Post by: sammyMaX on August 15, 2011, 05:26:21 pm

Is there any way to do this without brute-force factoring? Even with the fastest algorithm, GNFS (a very complicated one as well), it is predicted that 1024 bit semiprimes will not be factored for another 3 to 4 years, and that is on supercomputers. It is arguable that a community-wide (distributed computing) project could perform as fast as a supercomputer, but it would take such a long time that most people would drop out.

My idea is, can we view the Nspire decrypt the OS during an installation and obtain the private keys from there?

Title: Re: New RSA Algorithm discussion
Post by: AngelFish on August 15, 2011, 05:27:09 pm

The private keys are not located anywhere in the OS. That's why they're called private keys.

Title: Re: New RSA Algorithm discussion
Post by: sammyMaX on August 15, 2011, 05:30:51 pm

How does the Nspire update an OS without decrypting it? Decryption has to happen somewhere.

Title: Re: New RSA Algorithm discussion
Post by: fb39ca4 on August 15, 2011, 05:34:56 pm

It is not encrypted, it is digitally signed. On boot, the calculator verifies the signature of the OS, if even one byte of it was changed, the signature is invalid. We want to find the signing keys so we can make valid signatures of our own.

Title: Re: New RSA Algorithm discussion
Post by: sammyMaX on August 15, 2011, 05:37:37 pm

Does boot1 do this? If so, are we able to modify boot1?

Title: Re: New RSA Algorithm discussion
Post by: AngelFish on August 15, 2011, 05:48:24 pm

Boot1 is held in ROM, which is currently impossible to modify.

Also, the Nspire could indeed decrypt the OS if it wanted to (thank god it doesn't). It's enabled by something called Public-key cryptography, which basically allows anyone to verify/decrypt the data, but only those possessing the secret keys to sign the data so that it can be verified.

Title: Re: New RSA Algorithm discussion
Post by: sammyMaX on August 15, 2011, 05:50:55 pm

OS 2.1 and OS 3 modify the boot1 though; how does that happen?

EDIT: Fail. They modify the boot2.

Title: Re: New RSA Algorithm discussion
Post by: ExtendeD on August 15, 2011, 05:56:47 pm

Quote from: Qwerty.55 on August 15, 2011, 05:48:24 pm

Boot1 is held in ROM, which is currently impossible to modify.

It's actually a NOR chip. I thought some TI-Nspire diags software suggested the boot1 could be updated.

Title: Re: New RSA Algorithm discussion
Post by: sammyMaX on August 15, 2011, 05:57:30 pm

Yes. Here is the link: http://ourl.ca/8594 (http://ourl.ca/8594)

Title: Re: New RSA Algorithm discussion
Post by: AngelFish on August 15, 2011, 05:57:58 pm

That's why I said it's "currently impossible." To the best of my knowledge, no one knows how to do it.

Title: Re: New RSA Algorithm discussion
Post by: jnesselr on August 15, 2011, 06:22:29 pm

Right now, directly modifying it is impossible. It is also not within this discussion's range, as this is about generally breaking RSA, not necessarily the nSpire's RSA. Although, of course, it would be immediately applied to that.

Anyway, let me say this, since I have seen this question posed several times, and asked it several times myself before I knew completely about it.

There is currently no non-mathematical way of discovering the private keys

That is all. :D Well, actually, that's a lie. TI has them, but we don't advocate... retrieving... them.

But yeah, this is in the Math and Science sub-forum, so really should be pertaining to it. There is this (http://ourl.ca/9983) which is about bypassing the RSA signatures.

Title: Re: New RSA Algorithm discussion
Post by: sammyMaX on August 15, 2011, 06:28:49 pm

Quote from: graphmastur on August 15, 2011, 06:22:29 pm

That is all. :D Well, actually, that's a lie. TI has them, but we don't advocate... retrieving... them.

ROFL :hyper:

Title: Re: New RSA Algorithm discussion
Post by: sammyMaX on August 17, 2011, 05:30:15 pm

Here's a method a came up with: http://www.artofproblemsolving.com/Forum/viewtopic.php?f=149&t=425078 (http://www.artofproblemsolving.com/Forum/viewtopic.php?f=149&t=425078)

Title: Re: New RSA Algorithm discussion
Post by: AngelFish on August 17, 2011, 05:58:55 pm

Sorry to disappoint you, but verifying perfect squares is still far too computationally intensive to be practical.

To quote part of my post from the other page on the scale of the problem:

Quote

Given the current 2048 bit keys and classical computations, the scale of the problem is vastly more difficult than even the largest keys broken today (768 bits). By vast, I mean volume of the known universe measured in nanometers cubed vast*. The chance that anyone will solve it is so exceedingly slim that the only mathematical tool I have available to calculate it has to work with arbitrary precision operations simply in order to present it. Unless someone gets their hands on a massive quantum computer running Shor's algorithm**, it is, in short, an impossible problem.

*Even this is an understatement.

**It'd take about 30 seconds for a quantum computer to break the code, since the computations necessary increase according to (lg n)^3 for an n bit key.

Basically, trial integer factorization isn't going to work.

Title: Re: New RSA Algorithm discussion
Post by: sammyMaX on August 17, 2011, 08:20:42 pm

True, but you're missing the point here. I myself don't expect to find an algorithm that factors in polynomial time. But perhaps someone else could take my ideas and improve them. Knowledge is power, and I contributed what I did.