## [PrimeNumbers] Why encryption is now less secure than yesterday

Expand Messages
• Kevin Acres writes: I ve been working through the ramifications of my new algorithm and it seems that it can be used as an encryption busting tool. First, I m
Message 1 of 2 , Jun 30, 2004
Kevin Acres writes:
I've been working through the ramifications of my new algorithm and
it seems that it can be used as an encryption busting tool.

First, I'm not sure where the archives of the old list are, but you
might search them for mentions of my so-called "reverse method",
which, I believe, duplicates your new algorithm.

If anyone's still not seeing how it works, perhaps this will help. The
basic idea is simply to add an odd prime, in binary, to itself, shifted
each time so that the prime's units bit (always 1, since the prime is
odd) is under the 0 bit closest to the units bit of the sum-so-far.
Eventually, this will "force" the sum to be all 1's, which, of course,
is a Mersenne number. The smallest "realistic" example is 23, which is
10111 in binary (16 + 4 + 2 + 1):

0
+ 10111
= 10111
+ 10111
= 11001111
+ 10111
= 1000111111
+ 10111
11111111111

Since there are no 0's to the right of any 1 in this sum, we're done.

Note that the final sum has eleven 1's; therefore, 23 divides 2^11 - 1.
Note also that almost all primes lead to a string of 1's with a
composite length; a rather large fraction end up with a string of 1's
with a length of one less than the prime (e.g., 5's string of ones has
length 4).

My newest program that uses this method doesn't do it nearly this
directly; e.g., it factors the decremented input number and uses those
factors to predict the length (rather than calculating it using
addition and shifting as demonstrated above), which turns out to be
much faster (at least for larger input numbers).

encryption schemes or assist with factoring, I don't think I've seen or
heard those particular ideas anywhere before and they are certainly
interesting. I'd have to try some larger examples to get a better idea
of how helpful it is, however, which I won't have time to do for a few
weeks or more due to other commitments.

Hopefully I won't get the NSA knocking at my door because of this.

Well, they'd likely have knocked on my door years ago, so I think we're
safe.:) Here's the relevant parts of the RCS logs for my most recent
and my first "reverse method" programs. To give you a sense of how
long ago the first one was written, in 1989 I would have been running
\$750,000 retail (educational?) originally in 1981 or so) and DEC
MicroVax II's; MSWindows either didn't exist or wasn't at the Univ. of
Denver, though we did have some IBM AT's running MSDOS with an early MS
Flight Simulator.

Will

http://www.garlic.com/~wedgingt/mersenne.html

RCS file: RCS/1strs8.c,v
Working file: 1strs8.c
branch:
locks: strict
access list:
symbolic names:
keyword substitution: kv
total revisions: 59; selected revisions: 59
description:
Copy of 1strs6.c v1.86, about to be modified for larger
values (> 2^32) as factors.
----------------------------
revision 7.2
date: 2003/12/28 20:09:11; author: wedgingt; state: Exp; lines: +4 -4
Portability improvements noticed while compiling on Cygwin.
----------------------------
[...]
----------------------------
revision 1.2
date: 1999/02/08 00:48:39; author: wedgingt; state: Exp; lines: +184 -52
First pass at changes to allow arbitrarily large factors. Exponents
still limited to 2^64 - 1 (perhaps less), but that should be
sufficient for decades, expecially for composite exponents, which
are probably going to be < 2^15 for years.
----------------------------
revision 1.1
date: 1999/02/07 01:39:38; author: wedgingt; state: Exp;
Initial revision
=============================================================================
RCS file: RCS/1strs.c,v
Working file: 1strs.c
branch:
locks: strict
access list:
symbolic names:
keyword substitution: kv
total revisions: 3; selected revisions: 3
description:
Build the ones strings of primes given on stdin.
See comment at top for usage and output format.
----------------------------
revision 1.3
date: 1996/05/16 06:30:53; author: wedgingt; state: Exp; lines: +1 -1
Change to RCS Id.
----------------------------
revision 1.2
date: 1989/03/14 18:42:01; author: wedgingt; state: Exp; lines: +2 -2
Bug fix; was printing 'p' always.
----------------------------
revision 1.1
date: 1989/03/14 18:35:37; author: wedgingt; state: Exp;
Initial revision
=============================================================================
Your message has been successfully submitted and would be delivered to recipients shortly.