Ted Byfield wrote:

Subject:   [IRR] RIP RSA
Date:   Sun, 4 Feb 2001 17:53:12 -0500
From:   t byfield <tbyfield@panix.com>
To:   TBTF irregulars

maybe.

====================

Innocent readers:

First, apologies (if needed) to the authors and those in the chain of possession. The e-mail arrived rather poorly formatted, so I've put it out here for the TBTF Irregulars to review. Credit to Leo de Velez, Ron Rivest, Marc Branchaud, and Barry for bringing the material together.

Any errors in transcription are mine. (Although any errors in shift register theory are not :-)  

Gary Stock
gstock at seedmuse dot com

====================

IRREGULARS:

I've made an attempt at deconstructing the text Ted Byfield forwarded, strictly for ease of reading. It's always difficult following a forward of a forward of a... and a series of proofs and analyses in such a strange order is wacky.

I'd appreciate anyone taking a peek for corrections needed in the order of items [A] thru [K]. Also, if you see a structure that seems easier to read with different spacing, let me know. I'll clean it up for all to see.

This page is http://www.seedmuse.com/rsa_edit.htm

Thanks,

GS

[Update: Mon 01/02/05 13:30 -0500] I believe I've corrected the format of the table at the end of message [K]. The 72-char wrap/conversion of tabs/heehaw thang was causing me a little grief last night.


=====[A]=====
------- Start of forwarded message -------
From: "teammail" <leo@teammail.com>
To: <rivest@theory.lcs.mit.edu>
Subject: new way to decrypt RSA code
Date: Sat, 20 Jan 2001 17:02:41 +0800

Im Leo de Velez residing at 26B Prudent Lane, Sanville Subd, Quezon City, Philippines with phone number 63-917-532-9297. Im a math enthusiast and i found a new way to decrypt RSA encryption. The process involved three simple formulas. I have tried it on small values of N and it worked well and fast. It basically exploits the non-primeness of (p-1)(q-1). Using one of its factors, the secret key = can be calculated (forward direction).





=====[B]=====
------Original Message-----
From: Ron Rivest <rivest@theory.lcs.mit.edu>
Date: Sun, 21 Jan 2001 21:39:30 -0500
Subject: [leo@teammail.com: new way to decrypt RSA code]

I'd be curious to hear more---how does your method work??

Ron Rivest





=====[C]=====
------- Start of forwarded message -------
Date: Mon, 22 Jan 2001 13:44:03 +0800
From: "leo" <leo@teammail.com>
To: "Ron Rivest" <rivest@theory.lcs.mit.edu>
Subject: Re: [leo@teammail.com: new way to decrypt RSA code]

Dear Ron Rivest,

Thank you for your reply.

The first and second equations are similar to the equation used to calculate the secret key d from e and (p-1)(q-1). One difference is they do not need (p-1)(q-1).

And the third equation is a simple z= y/x, where z is the secret code. BUT z is not necessarily equal to d. This means secret codes are not unique.

I'm only using a pentium 100 laptop and an excel software to decipher secret key of N (value only up to 10^8). Its fast and instant.

Best regards, Leo de Velez





=====[D]=====
-----Original Message----
From: Ron Rivest <rivest@theory.lcs.mit.edu>
Date: Wed, 31 Jan 2001 00:49:09 -0500
Subject: [leo@teammail.com: Re: [leo@teammail.com: new way to decrypt RSA code]]

I don't understand your explanation at all. What is y? What is x?

Maybe you could explain how it works on the following example? n = 55 e = 3 ciphertext = 2

Thanks...

Thanks, Ron Rivest





=====[E]=====
==============================================================================
http://www.mb.com.ph/INFO/2001-02/IT020201.asp

Friday, 2 February 2001 Pinoy math enthusiast finds fast way to decode RSA encryption
By EDU H. LOPEZ
A Filipino mathematics enthusiast has developed a new method of decoding RSA (RivestShamir-Adleman) encryption using three simple formulas.

Leo de Velez has discovered these three formulas are simple forward equations that allow fast decoding of RSA encryption.

RSA is an Internet encryption and authentication system that uses an algorithm developed in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman.

The RSA algorithm is the most commonly used encryption and authentication algorithm and is included as part of the Web browser from Netscape and Microsoft.

It's also part of Lotus Notes, Intuit's Quicken, and many other products. The encryption system is owned by RSA Security. The company licenses the algorithm technologies and also sells development kits.

The technologies are part of existing or proposed Web, Internet, and computing standards.

Here's how the RSA system works. The mathematical details of the algorithm used in obtaining the public and private keys are available at the RSA Web site.

Briefly, the algorithm involves multiplying two large prime numbers (a prime number is a number divisible only by that number and through additional operations deriving a set of two numbers that constitutes the public key and another set that is the private key.

Once the keys have been developed, the original prime numbers are no longer important and can be discarded.

Both the public and the private keys are needed for encryption/decryption but only the owner of a private key ever needs to know it.

Using the RSA system, the private key never needs to be sent across the Internet. The private key is used to decrypt text that has been encrypted with the public key.

Thus, if I send you a message, I can find out your public key (but not your private key) from a central administrator and encrypt a message to you using your public key.

When you receive it, you decrypt it with your private key. In addition to encrypting messages (which ensures privacy), you can authenticate yourself to me (so I know that it is really you who sent the message) by using your private key to encrypt a digital certificate. When I receive it, I can use your public key to decrypt it.





=====[F]=====
-----------
At Friday, 2 February 2001, you wrote:

Hello again Leo --

I heard from a colleague that you have "gone public" with your claim to have a technique for decoding RSA ciphertexts (the information I received is copied below for your information).

It is curious to compare the situation here with similar claims that I received from a mathematician in Japan. Fortunately for him, he made the details of his proposed method available to me before going public with his conjectured claim, and I was able to explain the error in his thinking to him before he "went public"...

Perhaps you really do have a new technique here. If so, there are many people (including myself) who would be interested to see you provide some justification for your claims. Unfortunately, researchers in the field have seen all too many such claims evaporate when the details are made public. (Perhaps you recall, for example, the claims made by the Irish teenager Sarah Flannery a couple of years ago that received so much press attention.) So mere claims have little credibility until they are backed up by publication of the details and review by others in the field.

So, let me encourage you to proceed down the path you have started, and make public or post the details of what you think you can do. (If you prefer, I can look them over for you before you publish, but of course this is your show and you might just want to publish or post what you have.) If you would like a "challenge example" to work on, I could generate one. (How large would you like it to be?)

Your note to me earlier implied that you could thought you decrypt a significant fraction of the ciphertexts, but perhaps not all. Are you aware that the multiplicative properties of RSA then would imply that you could decrypt any ciphertext in polynomial expected time? (To decrypt ciphertext c, generate a random plaintext/ciphertext pair (p',c') using the public key, and decrypt c*c' with your technique, then divide the result by e' to obtain the desired ciphertext p corresponding to the target ciphertext c. Repeat as necessary.)

Anyway, I look forward to hearing more. I encourage you to publish what you have and take your congratulations or lumps, as appropriate... Of course, please keep me informed of what you do, and feel free to contact me with details if you want feedback directly from me... And don't be too embarassed if the details don't actually work out in the end--you wouldn't be the first. The truth will win out in the end, for all of us...

Cheers, Ron Rivest





=====[G]=====
----------
Date: Sat, 03 Feb 2001 12:07:59 +0800
From: "leo" <leo@teammail.com>
To: "Ron Rivest" <rivest@theory.lcs.mit.edu>
Subject: new way to decrypt RSA

Dear Ron,

The solution to 2^D = 1 mod N

There are two approaches that I am looking at.

The first is to multiply the binary code of N with another number so that the result will all be binary 1. This means adding the binary code of N while shifting to the left. This will give a number and add 1 will give a power of 2 (log base 2 is discrete). The discrete log is a factor of (p-1)(q-1). At least one half, usually one forth, one sixth, or one eighth of (p1-)(q-1).

For N=55 = 110111 Multiple = 19065 = 100101001111001

Although the operation is simple and fast (add and shift), the number of operation is in the order of 2^N / 5 . The operation is also not easy to distribute.

Another approach is to use the log N base 2.

Using Nroot = [sqr(int(sqrtN))] and Ndelta = [N-sqr(int(sqrtN))] and L = int(LOG(N,2))

i=1
  Starting point X = Nroot - i * Ndelta j = 0 to Ndelta/LOG(N,2) Y = X + j * L
  Calculate Z = LOG((MOD((2^Y),N),2)
  If Z is discrete, the D = Y - Z (check 2^D = 1 mod N)

i=2 (another computer doing this)
  Starting point X = Nroot - i * Ndelta j = 0 to Ndelta/LOG(N,2) Y = X + j * L
  Calculate Z = LOG((MOD((2^Y),N),2)
  If Z is discrete, the D = Y - Z (check 2^D = 1 mod N)

i= up to int(N/Ndelta) (another computer doing this)
  Starting point X = Nroot - i * Ndelta j = 0 to Ndelta/LOG(N,2) Y = X + j * L
  Calculate Z = LOG((MOD((2^Y),N),2)
  If Z is discrete, the D = Y - Z (check 2^D = 1 mod N)

I would appreciate if you can share with me a faster way of finding 2^D = 1 mod N

Best regards, Leo





=====[H]=====
==============================================================================
To: Ron Rivest <rivest@theory.lcs.mit.edu>
From: Leo de Velez <leo@teammail.com>
Subject: Re: "RSA Broken" ??
Reply-To: leo@teammail.com
CC: leo@lessonsplus.com
Date: Sat, 3 Feb 2001 16:16:42 +0800

Dear Ron,

I was surprised by the article because my agreement with Edu Lopez over the phone was that I will email him the explanation after i discuss the findings with you. Anyway, without the knowledge of this press report, I sent you this morning the approach that I am looking at.

It was basically finding X such that 2^X = 1 mod N

After the hard part above, then, finding Y such that X * Y = 1 mod E (using extended euclidian algorithm) and then, finding D = ( X * Y + 1 ) / E

As I have said before, D is not necessarily equal to private key (d). This means, other keys can decipher the code. The decoding may not be 100% but based on my few tests, it is above 80%. Another thing is X is a factor of (p-1)(q-1). It is at least one half but usually one fourth or one sixth or one eight. This means that the true private key can be calculated easily by multiplying X by two's and three's.

I also stated in my email this morning that I am investigating two approaches to find the X in 2^X = 1 mod N.

One is using the Linear Feedback bit Shift Register. The intention is to find a number Z such that Z * N = all binary bits are equal to 1. This is done by repeated addition of binary code of N to N while moving the addend to the left such that the bit 1 of addend is in line with the 0 bit of the partial sum.

The number Z is the decimal representation of the shifting of the addend. Then Z*N + 1 is a perfect log witch is the number of resulting binary digits. This is now the X that I am looking for.

As I have said, the number of operations involved is in the order of 2^N / 5. Even though each operation is very fast because it is binary and simple, the number of operations is enourmous. But it will still be faster by about = 2 * LOG(N,2) versus a simple division factorization.

The other approach is to use the LOG(N,2)

Starting from the Square(integer(square root of N)) and going down by jumps of LOG(N,2). The work can be broken up to different computers.

The intention again is to find 2^X = 1 mod N but the testing of X is in jumps of LOG(N,2). Once 2^X mod N is equal to a discrete LOG of 2, (2^X > = 2^y mod N), then we just subtract y from X to find the usuable X that > will give 2^X = 1 mod N. This will increase the speed of factorization > by at least LOG(N,2) times versus normal division factorization approach.

Then, by using the similar formula above, D can be calculated very fast and again D is not necessarily equal to the private key (d). As mentioned, it implies that other key can read the coded message but not 100%.

When I sent you my previous emails, I was still hoping that the extended euclidian algorithm will allow me to approach a good candidate for X which is a factor of (p-1)(q-1). However, as I use bigger numbers, the number of iterations became larger. The second approace was just a more stable replacement to that.

I am sure there is a faster way to find 2^X = 1 mod N out there and I would appreciate if you can help me on this. What I believe I can claim as mine is the 2^X = 1 mod N approach to find d and in so doing, finding also D that can replace d at least 80% of the time. The serious implication is that the private key is not unique at least for 80% of the messages.

Best regards, Leo de Velez





=====[I]=====
Ron Rivest wrote:

Dear Leo --

Thanks for the more detailed explanation of your approach to attacking RSA given in your emails (copied below). For the reasons I will explain, and as you are perhaps aware, I think your approach is unlikely to work in practice against large RSA numbers. It would be very premature or misleading to characterize RSA as "broken" based on your work to date.

On the other hand, the strength of a cryptosystem can only be determined by subjecting it to extensive analysis and attack by all interested parties. I encourage you (and others) to try and find a "shortcut" for breaking RSA faster than the known attacks (which also don't work in practice when the numbers are large). Perhaps you will someday find an attack that works efficiently. (Of course, I rather hope you won't, but I don't want to discourage you from trying!)

Let's go through some of the math and complexity issues.

To begin with, you note that there may be several exponents that work at decryption, and that the set of possible decryption exponents may depend on the message. This is well-known.

Let n = p*q, where p and q are prime.

Let m be a "message", i.e. a number in the range 0 to n-1.

For an arbitrary positive integer s and an integer r in the range 0 to s-1, define order(r,s) as the number of distinct values that occur in the sequence generated by r by multiplication: r, r^2, r^3, ... (all modulo s).

Thus
  order(2,5) = 4 as 2 generates the sequence 2,4,3,1,2,4,3,1,... (mod 5)
  order(2,8) = 3 as 2 generates the sequence 2,4,1,2,4,1,... (mod 8)
  order(3,6) = 1 as 3 generates the sequence 3,3,3,3,... (mod 6)
  order(0,5) = 1 as 0 generates the sequence 0,0,0,... (mod 5)

One can also call order(r,s) the order of the subgroup generated by r, modulo s.

(I note for the record here that this definition is a slight extension of the more usual one in that it covers the case that r is not relatively prime to s.) When r and s are relatively prime, we have r^order(r,s) = 1 (modulo s) and order(r,s) is the least positive exponent for which this works.

In any case we have that for any nonnegative integer k) r^(1+k*order(r,s)) = r (modulo s) and (1+k*order(r,s)) are the only exponents for which this works.

Thus, for a message m modulo n, we have that m^(1+k*order(m,n)) = m (mod n) for all nonnegative integers k.

For RSA encryption/decryption to work with message m, we need that c^d = m (mod n) where c is the ciphertext c = m^e (mod n) In other words, we need that m^(ed) = m (mod n) So it must be the case that ed = 1 + k*order(m,n) for some nonnegative integer k.

What values can order(m,n) have?

It is known that when p is prime order(m,p) must be a divisor of p-1, and that for any divisor v of p-1 there is some message m such that order(m,p) = v. More precisely, the number of messages m modulo p such that order(m,p) = v is precisely equal to phi(v) when v>1, and equal to 2 when v=1, where phi(v) is the Euler totient function of v (the number of positive integers less than v that are relatively prime to v). When v=1, the elements 0 and 1 both have order(0,p)=order(1,p)=1.

In the interesting case that p is a Sophie-Germain prime, so that p = 2p'+1, where p' is also prime, then p-1 = 2p' and all elements have order 1, 2, p' or 2p'. Furthermore 2 elements have order 1 (these are 0 and 1) 1 element has order 2 (this is p-1, i.e. -1 mod p) p'-1 elements have order p' p'-1 elements have order 2p' so all but the three elements 0, 1, and -1 (which have the obvious orders 1, 1, and 2) have order divisible by p'. It is often recommended that users of RSA use such primes.

Now for RSA, when n = pq, we have order(m,n) = lcm(order(m,p),order(m,q)) where lcm(a,b) = ab/gcd(a,b) = the least common multiple of a and b.

In the case that p and q are Sophie-Germain, p=2p'+1, q=2q'+1, where p' and q' are prime, then the possible values of order(m,n) are 1 2 p' 2p' q' 2q' p'q' 2p'q' There are four elements of order 1 and eight elements of order 2. All other orders have order divisible by p' or q', and so are large and very hard to find without knowing p or q.

To find a decryption exponent d that works for a message m, we can pick and d satisfying ed = 1 + k*order(m,n) as noted above. This is equivalent to: d = e^{-1} mod(order(m,n)) (*) Given the possible variation in the values of order(m,n) and the possible variation in the choice of k above, we see that there can be variation in decryption exponents that work.

However, if we want to choose a decryption exponent that works for *all* messages m, then we need to use the fact that order(m,n) is a divisor of lcm(p-1,q-1) and that all such orders are possible. Denote lambda(n) = lcm(p-1,q-1) Then if we solve the equation d = e^{-1} mod (lambda(n)) (**) we get a result that satisfies (*) for all messages m. This is the usual procedure. It is also the case that solving d = e^{-1} mod (phi(n)) where phi(n) = (p-1)*(q-1) will give a solution that also satisfies (**) and thus satisfies (*) for all m. Working mod lambda(n) can save a little bit over working modulo n, but typically not much, since gcd(p-1,q-1) is typically small.

This explains your observation that there may be several decryption exponents that work, and that even some decryption exponents work for some messages and not for others. In the case of large Sophie-Germain primes, however, almost all (all but approximately p+q) messages will have order(m,n) divisible by p'q', and the set of decryption exponents that "work" for m will satisfy e*d = 1 (mod p'q').

Now, on to your proposed attack method, which is, as you note, not so efficient for a large n. I would like to argue here that your method is not likely to be efficient, given the state of the art.

You propose first finding an x such that 2^x = 1 (mod n) (***) and then proceeding from there.

** This is a "known hard problem" with no good solutions known, even ** though many have tried. It is known as the "discrete logarithm problem" ** and appears to be just as hard as factoring the modulus n.

Using the above notation, we must have that x is a multiple of order(2,n) for (***) to hold. In the case that p and q are Sophie Germain, this means that you are finding p'q' or a small multiple of p'q'. Suppose that you actually found p'q' this way. Then of course n = pq = (2p'+1)(2q'+1) = 4p'q' + 2p' + 2q' + 1 so you could then compute (n - 4p'q' - 1)/2 = p'+q' Now, given the product p'q' of p' and q', and the sum p'+q' of p' and q', it is easy to compute p' and q' separately. This means you have factored n, since p and q are 2p'+1 and 2q'+1.

Thus, in order to get started on your attack method, you need to solve the discrete logarithm problem, which is believed to be hard, and is likely to lead (as you see) to a factorization of n. Indeed, it is known that finding any multiple of lambda(n) can lead to a factorization of n, so that you really are doing nothing more than proposing factoring n as a way of getting started on breaking RSA.

The "usual division approach" for factoring n that you mention is of course not the best approach to factoring n, and not what you should be considering as a "competitor" to your approach. Indeed the "number field sieve" and its generalizations can factor a number n in time exp(c (ln n)^(1/3) (ln ln n)^(2/3) where c = 1.92 and ln(x) is the natural logarithm of x. This is *much* faster than trial division, but is not fast enough to allow factorization of 1000-4000 bit numbers...

While you thought you were attempting some "new" way of attacking RSA, the method you propose is in fact equivalent to the "old" way of attacking RSA: factoring the modulus n. There doesn't seem to be any new leverage you are getting by thinking about the problem in the way you propose. There is no reason to think that finding an x which is a multiple of order(2,n) is any easier than directly finding the factors p and q of n. (Indeed, order(2,n) must be divisible by p'q' in the case that p and q are Sophie-Germain...)

So, I hope this helps you think more clearly about the issues raised in your proposed attack.

There are many good references for this sort of thing; one of my favorites is:

book {Pomerance90, editor = {Carl Pomerance}, title = {Proc.\ of the {AMS} Symposia in Applied Mathematics: Computational Number Theory and Cryptography}, publisher = {American Mathematical Society}, year = {1990} }

I think it is still in print.

Some minor notes: I think properly when p=2p'+1 we should call p' the Sophie-Germain prime and not p. And the sort of reasoning applied above using Sophie-Germain primes is a good guide for you, but the arguments against your approach would apply in any case, as long as p-1 and q-1 have large prime factors (which they are likely to do in general, even if p and q are chosen essentially at random).

Cheers, Ron Rivest





=====[J]=====
Date: Sun, 4 Feb 2001 09:52:07 +0100 (CET)
From: Barry <barry@xs4all.nl>
To: cryptography@c2.net
Subject: Re: Pinoy math enthusiast finds fast way to decode RSA encryption

Quoting Marc Branchaud <marcnarc@xcert.com>:
> Anyone know if there's any truth to this?
>
> Marc
>
>
> MANILA BULLETIN: http://www.mb.com.ph/INFO/2001-02/IT020201.asp
>
> Pinoy math enthusiast finds fast way to decode RSA encryption
> At 03-02-01 02:27, Marc Branchaud wrote:

After finding his e-mail adres, I just asked him :
From: Leo <leo@teammail.com>
To: barry@xs4all.nl, leo@teammail.com
Subject: [Fwd: Re: RSA Broken ??]

Dear Barry Wels,

For your information and further discussion and scrutiny. Here is a copy of my communication with Ron Rivest.

The format of the illustration below seems to have been modified by my email software.

Best regards,
Leo





=====[K]=====
-------- Original Message --------
Subject: Re: RSA Broken ??
Date: Sun, 04 Feb 2001 06:59:11 +0800
From: Leo <leo@teammail.com>
To: Ron Rivest <rivest@theory.lcs.mit.edu>
References: <200102031932.OAA20818@loon.lcs.mit.edu>

Dear Ron,

Thank you very much for the clarification and comprehensive explanation of the math concepts behind RSA. I really appreciate the time you spend on this communications.

I just would like to get additional view and maybe some idea on comparative speed of the process I proposed of multiplying N by Y such that the product is all bit 1 to solve 2^X = 1 mod N. This, I believe, is really a "NEW" approach to find the private key. The "NEW" here is the Specific Use of 2 and the Use of simple Add-Shift-Compare binary operations to find X.

To illustrate further:

Say N = 55 = 110111

By repeated addition and shifting, we arrive at Y = 19065 = 100101001111001

  
                  110111    = bit 0 of Y = 1
  +            110111       = bit 3,2,1 of  Y = 100
  ------------------------
               111101111
  +           110111        = bit 4 of Y = 1
  ------------------------
             10101011111
  +          110111         = bit 5 of Y = 1
  ------------------------
            110000111111
  +         110111          = bit 6 of Y = 1
  ------------------------
           1100111111111
  +      110111             = bit 9,8,7 of Y = 100
  ------------------------
        1000011111111111
  +    110111               = bit 11, 10 of Y = 10
  ------------------------
      100011111111111111
  + 110111                  = bit 14,13,12 of Y = 100
  ------------------------
    11111111111111111111    = 20 bits of 1, so X = 20


I believe this is a very fundamental function of a computer (add, shift and compare). Therefore, I believe this is a lot faster than a multiplication or division factoring approach. I just don't have any clue on how to compare this speed with "number sieves". Although it seems like a factoring approach for N, the operation is forward (addition) and one time (no trial and error). So, I believe should be very fast. My estimate is at least = LOG(N,2) * 2 faster than division factoring. To help me compare, maybe, you can give a clue on how fast is a "number sieve" approach compared with simple division.

Again, thank you very much for your valuable time spent on this. I really appreciate it.

Best regards,
Leo

# # #

Thanks for server space to SeedMuse, The Business Plan for Geek Entrepreneurs™