From msuinfo!gmi!zombie.ncsc.mil!news.mathworks.com!udel!gatech!howland.reston.ans.net!wupost!waikato!auckland.ac.nz!news Sat Nov 12 13:14:14 1994 Path: msuinfo!gmi!zombie.ncsc.mil!news.mathworks.com!udel!gatech!howland.reston.ans.net!wupost!waikato!auckland.ac.nz!news From: Raul Deluth Miller Newsgroups: sci.crypt.research Subject: RSA weaknesses? Date: 10 Nov 1994 05:55:42 GMT Organization: - Lines: 46 Sender: crypt-submission@cs.aukuni.ac.nz (sci.crypt.research co-moderator) Approved: crypt-submission@cs.aukuni.ac.nz Message-ID: <39scku$mfc@net.auckland.ac.nz> Reply-To: Raul Deluth Miller NNTP-Posting-Host: cs13.cs.aukuni.ac.nz X-Newsreader: NN version 6.5.0 #7 (NOV) Given: p -- large prime number q -- large prime number e -- number relatively prime with respect to (p-1)(q-1) d -- number such that 1=de mod (p-1)(q-1) n -- pq x -- some random positive integer less than n ("plaintext") y -- n|x^e ("cyphertext") Signifying a mod b with b|a, and ab with a*b, and performing calculations from right to left with no precedence rules .. the sequence: n|y*n|y*n|y*n|y*n|y*n|y*n|y*n|y*n|y*...n|y*n|y*n|y*n|y*n|y with y repeated for d occurances will produce x as a result. This is only guaranteed to work for a number d selected as described above. However, looking at the result of intermediate n|... calculations above, x will occur as an intermediate result some k times where k is a factor of (p-1)(q-1). The interval between these occurances will be j where jk=(p-1)(q-1). This suggests the potential viability of a hill-climbing algorithm to determine factors of (p-1)(q-1), which may in turn lead to a factorization of n. Alternatively, this property might be directly exploited, especially if: (a) the probability of the revelation of plaintext is significantly higher than the probability of factorization, and (b) some technique is available (statistical analysis or knowledge of the form of the plaintext) to recognize a plaintext when it appears. I presume that this property of RSA has been discussed in the literature -- however, I've not been able to find any such discussion. Does anyone know of any literature on this topic? -- Raul D. Miller N=:((*/pq)&|)@ NB. public e, y, n=:*/pq P=:*N/@:# NB. */-.,e e.&factors t=:*/<:pq 1=t|e*d NB. pq is two large primes, e medium x-:d P,:y=:e P,:x NB. (d P,:y)-:D P*:N^:(i.#D)y [. D=:|.@#.d From msuinfo!agate!darkstar.UCSC.EDU!news.hal.COM!decwrl!waikato!auckland.ac.nz!news Sat Nov 12 13:14:30 1994 Path: msuinfo!agate!darkstar.UCSC.EDU!news.hal.COM!decwrl!waikato!auckland.ac.nz!news From: warlord@MIT.EDU (Derek Atkins) Newsgroups: sci.crypt.research Subject: Re: RSA weaknesses? Date: 12 Nov 1994 17:43:15 GMT Organization: Massachusetts Institute of Technology Lines: 45 Sender: crypt-submission@cs.aukuni.ac.nz (sci.crypt.research co-moderator) Approved: crypt-submission@cs.aukuni.ac.nz Message-ID: <3a2urj$k14@net.auckland.ac.nz> References: <39scku$mfc@net.auckland.ac.nz> Reply-To: warlord@MIT.EDU (Derek Atkins) NNTP-Posting-Host: cs13.cs.aukuni.ac.nz X-Newsreader: NN version 6.5.0 #7 (NOV) In article <39scku$mfc@net.auckland.ac.nz> Raul Deluth Miller writes: Signifying a mod b with b|a, and ab with a*b, and performing calculations from right to left with no precedence rules .. the sequence: n|y*n|y*n|y*n|y*n|y*n|y*n|y*n|y*n|y*...n|y*n|y*n|y*n|y*n|y with y repeated for d occurances will produce x as a result. This is only guaranteed to work for a number d selected as described above. Well, right -- this is a brute force attack. Just keep trying every value until you find it. Of course this is going to work, since you have a finite space in which to search. The problem is that the size of the numbers here make this approach prohibitive. However, looking at the result of intermediate n|... calculations above, x will occur as an intermediate result some k times where k is a factor of (p-1)(q-1). The interval between these occurances will be j where jk=(p-1)(q-1). This is a perfect reason why you want "good primes" -- choose p and q such that p=p1*p2+1, or something like that (I forget the actual equation offhand). This forces phi(n) such that given e there are only two possible values for d, which maximizes your search space. This suggests the potential viability of a hill-climbing algorithm to determine factors of (p-1)(q-1), which may in turn lead to a factorization of n. Again, this is a brute-force method. If there are only 2 values for d that will work, then you are looking for two values out of what? 2^|n|? Ok, so you have a 1 in 2^|n|-1 chance in finding the value. The time it would take to search this space makes it prohibitive, since the search space is practically flat. -derek -- Derek Atkins, SB '93 MIT EE, G MIT Media Laboratory Member, MIT Student Information Processing Board (SIPB) Home page: http://www.mit.edu:8001/people/warlord/home_page.html warlord@MIT.EDU PP-ASEL N1NWH PGP key available From msuinfo!agate!darkstar.UCSC.EDU!news.hal.COM!decwrl!waikato!auckland.ac.nz!news Sat Nov 12 13:15:11 1994 Path: msuinfo!agate!darkstar.UCSC.EDU!news.hal.COM!decwrl!waikato!auckland.ac.nz!news From: ken@chinook.halcyon.com (Ken Pizzini) Newsgroups: sci.crypt.research Subject: Re: RSA weaknesses? Date: 12 Nov 1994 17:45:55 GMT Organization: What, me? Lines: 40 Sender: crypt-submission@cs.aukuni.ac.nz (sci.crypt.research co-moderator) Approved: crypt-submission@cs.aukuni.ac.nz Message-ID: <3a2v0j$k22@net.auckland.ac.nz> Reply-To: ken@chinook.halcyon.com (Ken Pizzini) NNTP-Posting-Host: cs13.cs.aukuni.ac.nz X-Newsreader: NN version 6.5.0 #7 (NOV) In article <39scku$mfc@net.auckland.ac.nz>, Raul Deluth Miller wrote: [...] >Signifying a mod b with b|a, and ab with a*b, and performing >calculations from right to left with no precedence rules .. the >sequence: > n|y*n|y*n|y*n|y*n|y*n|y*n|y*n|y*n|y*...n|y*n|y*n|y*n|y*n|y >with y repeated for d occurances will produce x as a result. This is >only guaranteed to work for a number d selected as described above. > >However, looking at the result of intermediate n|... calculations >above, x will occur as an intermediate result some k times where k is >a factor of (p-1)(q-1). The interval between these occurances will be >j where jk=(p-1)(q-1). Let's look at the magnatude of the numbers involved. I'll assume that n is approximately 300 digits long, being composed of a 140 digit p and a 160 digit q. If our public e is about 100 digits long, we should expect our private d to be about 200 digits long, since (p-1)(q-1) is about 300 digits, e*d must be greater than (p-1)(q-1), and e should be less than (p-1)(q-1). So to directly search for d by the long equation above would take prohibitively long. (The calculation of e**x mod n is usually done by much faster techniques such as repeated squaring.) So the question becomes: is j small enough that a search is feasible? The answer depends on whether (p-1)(q-1) contains small factors. If the smallest factor of (p-1)(q-1) is, say, 25 digits, then searching for an instance of x is not feasible. If the smallest factor is about 6 digits, then this approach holds the potential of being feasible. This argues for the reinstatment of the guideline for choosing n that (p-1)(q-1) should not have small factors. --Ken Pizzini