Loading ...
Sorry, an error occurred while loading the content.

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

Expand Messages
  • Will Edgington
    Jun 30, 2004
    • 0 Attachment
      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).

      As for your thought about your "new algorithm" being used to break
      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
      it on DEC Vax11/750's (minicomputers, about 0.8MHz(?) CPUs, about
      $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
      head: 7.2
      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
      head: 1.3
      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
      =============================================================================
    • Show all 2 messages in this topic