Re: Pinoy math enthusiast finds fast way to decode RSA encryption

[Markus Senoner]

On Tue, 6 Feb 2001, Padmapani S Ganti wrote:
> I just wanted to add a thing to the prime number which i found
> independently and i do not know whether this has been achieved earlier or
> not but i have a way of proving that every prime is of the form
> (int)sq.root(1+24n)

May I add, that every prime is of the form (int)(1+n),
which is much more simpler to calculate.  I can prove this too.  :-)

Your formula simply gives a list of *all* numbers (some even multiple
times, the bigger n, the more results: for n=7 and n=8 both give 13,
while for n=6, the formula gives 12, which is not a prime).

:-)
Markus
--

Re: Pinoy math enthusiast finds fast way to decode RSA encryption

[Thomas Quinot]

Le 2001-02-07, Padmapani S Ganti écrivait :

> I just wanted to add a thing to the prime number which i found
> independently and i do not know whether this has been achieved earlier or
> not but i have a way of proving that every prime is of the form
> (int)sq.root(1+24n)

Not very interesting, since every integer >= 12 is of that form...

let x integer >= 12.
(x+1)^2 = x^2 + 2x + 1 > x^2 + 24
Therefore there is one N = 1 + 24n which satisfies
x^2 <= N < (x+1)^2
ie x <= sqrt (N) < x+1, which is the definition of
x = int (sqrt (N)).

Thomas.

--
[EMAIL PROTECTED]

Re: Pinoy math enthusiast finds fast way to decode RSA encryption

[Lacroix, Robert]

In response to Taneli Huuskonen [mailto:[EMAIL PROTECTED]]

Sorry to inflict this crapto on you.  I came up with the algorithm when I
read Ariel Waissbein's post.

Waissbein said...
check if a number of size 2^1024, e.g. 2^(2^1024), is
congruent to 1 modulo the public exponent n. Hence you
at least need to store 2^1024 digits in your computer
which is a more than a lot.

I knew about generators of cyclic groups, but I was inspired by the need for
a solution to 2^X = 1 mod N, and I thought of shift-and-add on least
significant zero bits as a way of generating a covering of the bitmap of all
ones.  Talk about synchronicity...  I wrote and posted, then I ran out for
dinner (yes, you can flame me for not doing the literature search).  Later,
I read through the web links, and saw that the solution was identical to the
one of de Velez that was torn apart by Rivest a day before (well, almost
synchronous).

I don't recall seeing de Velez's method explicitly discarding the low order
one bits to conserve memory once they are not needed.  His inspiration
clearly comes from shift registers, so he could have defended his design by
observing that he could discard low order bits, but he didn't, and he caved
in to the experts.  So I won't give him credit for that part, but he did
come up with shift-and-add first.

I violated the memory space constraint with the following snippet of code:

> # complete the solution.
> $b = $a * $n + 1;
> $x = -1;
> while ($b != 0) {
> $b >>= 1;
> $x++;
> }

It should be replaced with:

# complete the solution.
$x = $p;
$b++;# this is a power of 2
while ($b != 1) {
$b >>= 1;
$x++;
}

Please look over the code again.  I wrote it to refute the argument that you
need to concurrently store all the digits for 2^X, which it doesn't, in
deriving the number 'a', in aN + 1.  The low order one bits of 2^X - 1 are
discarded by a right shift after they have been computed and counted.  At
every step, the addition may produce a carry bit beyond the register, but
shifting restores the sum within the bounds.

> Sorry to be a wet blanket, but it should be "O(N) time".  As
> a factoring method, this is less efficient than trial division.

Wait a second.  I seem to have confused some folks about what the above
algorithm accomplishes.  It doesn't break RSA, it solves a problem in number
theory.  And it doesn't take O(N).  At worst, the outer loop is once per bit
of N (ie. log N) and the inner loop counts bits of N (again, log N).  Ergo,
the routine runs in time O(log N)^2.  If in breaking RSA, some specific
value of X is required other than the one that this routine finds, then yes,
you'll need to keep shifting and adding to find ever larger values of 'a'
and X.  But I thought that this value of X is the order of 2, and that 2 is
a generator of the cyclic group 1 (mod N).  I will humbly accept your
corrections in public, for the benefit of all.


Robert Lacroix

Re: Pinoy math enthusiast finds fast way to decode RSA encryption

[Padmapani S Ganti]

Hi Everybody.,
I just wanted to add a thing to the prime number which i found
independently and i do not know whether this has been achieved earlier or
not but i have a way of proving that every prime is of the form
(int)sq.root(1+24n)
of course excepting 2 and 3.This is a result derived from the fact that
every prime has to be of the form 6n+1 or 6n-1 . I used GNU Octave on a
LInux box o generate 70 primes scanning 2000 values of n in a second and i
am still finding ways of improving on this.any comments on this one i
would most gladly answer them.Thank you for the time

Padmapani S Ganti
George Mason University.,
Fairfax, VA 22030-
703 993 1681
mason.gmu.edu/~pganti

Re: Pinoy math enthusiast finds fast way to decode RSA encryption

[Taneli Huuskonen]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

"Lacroix, Robert" <[EMAIL PROTECTED]> writes:

> # This algorithm efficiently solves problems of the form 2^x = aN + 1,
> # using O(log N) storage and O(log N)(log N) time.

Sorry to be a wet blanket, but it should be "O(N) time".  As a factoring
method, this is less efficient than trial division.

Taneli Huuskonen

-BEGIN PGP SIGNATURE-
Version: PGPfreeware 5.0i for non-commercial use
Charset: noconv

iQA/AwUBOoEP9V+t0CYLfLaVEQLX3gCfcHHps/Rh8gI+4si0GI1qGbTH8FsAoMkx
+4Z1jLiJt+cgnwHqvS/b2XeB
=Zant
-END PGP SIGNATURE-
--
I don't   | All messages will be PGP signed,  | Fight for your right to
speak for | encrypted mail preferred.  Keys:  | use sealed envelopes.
the Uni.  | http://www.helsinki.fi/~huuskone/ | http://www.gilc.org/

Re: Pinoy math enthusiast finds fast way to decode RSA encryption

[Lacroix, Robert]

#!/usr/local/bin/perl -w

# getcycle.pl
# (Copyright) Robert A. Lacroix, Feb. 6, 2001; Winnipeg, Canada
# This algorithm efficiently solves problems of the form 2^x = aN + 1,
# using O(log N) storage and O(log N)(log N) time.
# I am reinventing the wheel, or is it "Goodbye, RSA?"
# Input restrictions: argument N must be a positive odd integer.
# This implementation is subject to machine word size overflow.
#
# Happy Birthday, Vonne.

use integer;

local ($i, $n, $a, $b, $c, $k, $p, $x);

$n = $ARGV[0];

if (($n & 1) == 0) { die "$n is even\n"; }

$a = 0; # multiple of N
$b = 0; # partial 2^x; actually uses 2(log N) bits at a time.
$p = 0; # bit shift offset
$i = 0; # iteration count

while (1 == 1) {
$k = (($b + 1) & ~$b);  # mask for least significant 0 bit
last if ($k > 1 && $k == $b+1);   # loop exit condition
$a |= $k << $p; # merge into result
$c = -1;# determine bit position (base offset 0)
while ($k != 0) {
$k >>= 1;
$c++;
}
$p += $c;   # cumulative offset
$b = ($b >> $c) + $n;
$i++;
}

# complete the solution.
$b = $a * $n + 1;
$x = -1;
while ($b != 0) {
$b >>= 1;
$x++;
}

print "2^$x = $a * $n + 1 in $i iterations\n";

sample run:
getcycle.pl 231
2^30 = 4648233 * 231 + 1 in 12 iterations

Re: Pinoy math enthusiast finds fast way to decode RSA encryption

[Alan Day]

I doubt it...

http://www.seedmuse.com/rsa_edit.htm


-Original Message-
From: Andre Delafontaine [mailto:[EMAIL PROTECTED]]
Sent: Monday, February 05, 2001 11:02 AM
To: [EMAIL PROTECTED]
Subject: Pinoy math enthusiast finds fast way to decode RSA encryption


The following link was sent to me this morning.

Has anybody heard about this, gotten any more info?

Is this TRUE? :-)

http://www.mb.com.ph/INFO/2001-02/IT020201.asp

Andre
--
 andre.delafontaine at echostar.com

  F20 DSS: BD75 66D9 5B2C 66CE 9158  BB27 B199 59CE D117 4E9F
   F16 RSA: F8 04 FE 50 02 B5 03 02  F6 87 C7 8D F9 2E B8 58

Re: Pinoy math enthusiast finds fast way to decode RSA encryption

[Ariel Waissbein]

yes, but the attack does not work (efficiently). We analyzed
it together with Ariel Futoransky and Calos Sarraute and
judged it highly impractical (no complexity estimates could
be found on the post/news). Later we read a mail which was
signed by Rivest himself in which he said that the attack was
of a complexity worse than a brute force attack.

To understand more precisely, this attack finds cycles
of the form 1,2,2^2,...2^x,1. This integer x sheds info
about the private exponent, e.g. (x+1) serves as a private
exponent for a number of ciphertexts (but not all, only the
ones in the uncovered cycle) and is sometimes but not
always a multiple of the private exponent. Doing this
implies that --when using 1024 bits keys-- you have to
check if a number of size 2^1024, e.g. 2^(2^1024), is
congruent to 1 modulo the public exponent n. Hence you
at least need to store 2^1024 digits in your computer
which is a more than a lot.


Regards,
Ariel Waissbein



Andre Delafontaine wrote:
>
> The following link was sent to me this morning.
>
> Has anybody heard about this, gotten any more info?
>
> Is this TRUE? :-)
>
> http://www.mb.com.ph/INFO/2001-02/IT020201.asp
>
> Andre
> --
>  andre.delafontaine at echostar.com
>
>   F20 DSS: BD75 66D9 5B2C 66CE 9158  BB27 B199 59CE D117 4E9F
>F16 RSA: F8 04 FE 50 02 B5 03 02  F6 87 C7 8D F9 2E B8 58

--
===[ CORE Seguridad de la Informacion S.A. ]=
Ariel Waissbein
Researcher - Corelabs

email :  [EMAIL PROTECTED]
http://www.core-sdi.com
=

I was scared. Petrified. Because (x) hearing voices isn't like
catching a cold, you can't get rid of it with lemmon tea (y)
it's inside, it is not some naevus, an epidermal blemish you
can cover up or cauterise (z) I had no control over it. It was
there of its own volition, just stopped in and (zz) I was going
bananas.
-Tibor Fischer ``TheThought Gang"

--- For a personal reply use [EMAIL PROTECTED]

Re: Pinoy math enthusiast finds fast way to decode RSA encryption

[Stephen Clouse]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

On Mon, Feb 05, 2001 at 09:01:33AM -0700, Andre Delafontaine wrote:
> The following link was sent to me this morning.
>
> Has anybody heard about this, gotten any more info?
>
> Is this TRUE? :-)
>
> http://www.mb.com.ph/INFO/2001-02/IT020201.asp

In what may be a sign of the impending apocalypse, Slashdot actually researched
a story.  Short version: the claim is bogus.  The Slashdot story below has a
brief explanation from Rivest, and a link to a much longer email exchange
between Rivest and our would-be cracker on the topic.

http://slashdot.org/articles/01/02/05/1911258.shtml

- --
Stephen Clouse <[EMAIL PROTECTED]>
Senior Programmer
The IQ Group, Inc. 

-BEGIN PGP SIGNATURE-
Version: PGP 6.5.8

iQA/AwUBOn7/4gOGqGs0PadnEQIJZwCbBPTYzY+avuTNq7RYGPnIOOSt2GAAn200
D+zk6z9AtNYgeM1XecNdBOzB
=RPsh
-END PGP SIGNATURE-

Re: Pinoy math enthusiast finds fast way to decode RSA encryption

[Howard Lowndes]

There is an extension to theis, explaining the thinking, at
http://www.mb.com.ph/INFO/2001-02/IT020601.asp

--
Howard.

LANNet Computing Associates 
   "...well, it worked before _you_ touched it!"

On Mon, 5 Feb 2001, Andre Delafontaine wrote:

> The following link was sent to me this morning.
>
> Has anybody heard about this, gotten any more info?
>
> Is this TRUE? :-)
>
> http://www.mb.com.ph/INFO/2001-02/IT020201.asp
>
> Andre
> --
>  andre.delafontaine at echostar.com
>
>   F20 DSS: BD75 66D9 5B2C 66CE 9158  BB27 B199 59CE D117 4E9F
>F16 RSA: F8 04 FE 50 02 B5 03 02  F6 87 C7 8D F9 2E B8 58
>

Pinoy math enthusiast finds fast way to decode RSA encryption

[Andre Delafontaine]

The following link was sent to me this morning.

Has anybody heard about this, gotten any more info?

Is this TRUE? :-)

http://www.mb.com.ph/INFO/2001-02/IT020201.asp

Andre
--
 andre.delafontaine at echostar.com

  F20 DSS: BD75 66D9 5B2C 66CE 9158  BB27 B199 59CE D117 4E9F
   F16 RSA: F8 04 FE 50 02 B5 03 02  F6 87 C7 8D F9 2E B8 58