Cryptography-Digest Digest #490, Volume #9 Sun, 2 May 99 16:13:03 EDT
Contents:
Re: Factoring breakthrough? (Robert Harley)
Re: Stream Ciphers and Quantum Computer Resistance ([EMAIL PROTECTED])
How to Save MAGENTA
Re: Paper on 512 cracking ("Roger Schlafly")
Re: Factoring breakthrough? (Terje Mathisen)
Re: Deadly threats ("hapticz")
----------------------------------------------------------------------------
From: Robert Harley <[EMAIL PROTECTED]>
Subject: Re: Factoring breakthrough?
Date: 02 May 1999 18:54:11 +0200
lcs Mixmaster Remailer <[EMAIL PROTECTED]> writes:
> Rumor has it Adi Shamir will announce factoring breakthrough soon.
> Increasing efficiency by orders of magnitude and breaking keys 100-200
> bits longer than current state of the art.
>
> Anybody confirm/deny?
I've no idea, but this reminded me of an implementation trick which
seems to be useful yet not widely known (at least I don't recall
having seen it written down).
It's how to do sieving in a cache-friendly way.
The way of sieving that everyone has been using for 10 or 15 years
doesn't take cache effects into account at all. As the speed of chips
continues to increase faster than the latency of main memory, a
cache-friendly method is bound to become more widespread eventually!
I'm not claiming any particular originality here but just describing
it for those interested.
Take the quadratic sieve. The standard method spends almost all its
time running through a table reading bytes, adding, and writing them
back. The table is typically on the order of 10 or 20 MB and the
accesses have no locality so each iteration takes at least as long as
a random access into main memory which takes 50 to 100 cycles these
days.
Suppose we want to sieve using a factor base of primes up to some
limit. About half of the primes are involved in two arithmetic
progressions and half in none (depending on quadratic residuacity) so
there are about the same number of progressions as primes. There will
be roughly 50000 if we take LIM = 600000. We give each progression a
16-bit index (note that for bigger factor bases we would have to go to
32-bit indices).
Now keep a table of these indices, whose length is a little bigger than
the largest prime in the factor base. In this case the table size
would be about 600000 x 16 bits which is about 1.2 MB (and fits easily
in the 2 MB cache on my machine).
Now we can scan through the table advancing each index by the prime
step (or prime-power step) associated with it, by looking the step up
in a small array (50000 x 32 bits = 200 KB, say).
Many of these steps are small and will happen in L1 or L2 cache (8K +
96K here). The largest ones advance by a maximum of 1.2 MB. Note
that the steps don't run off the end of the table - instead just wrap
them around the end and back to the beginning. Everything fits in L3
cache and main memory doesn't come into it at all! Since the latency
of L3 cache is four times better than that of main memory, this is
good. =:-)
To keep track of the progressions that touch a given number, use
another small array to build linked lists. When we read an index out
of the table, then a list of indices can be traversed by following
links like this: index = next[index] until the index becomes zero (a
value reserved for this purpose which is not the index of any
progression).
In pseudo-C the code would look like the following snippet (which
doesn't do anything useful yet!)
==============================================================================
j = 0;
for ever {
index = table[j];
table[j] = 0;
while (index) {
nextIndex = next[index];
tmp = j + step[index]; if (tmp >= LIM) tmp -= LIM; /* Wrap around. */
next[index] = table[tmp];
table[tmp] = index;
index = nextIndex;
} /* end while */
++j; if (j == LIM) j = 0; /* Wrap around. */
} /* end for */
==============================================================================
Now with each progression we also associate the logarithm of its
prime. These don't have to fit in a byte and can be quite precise,
for instance round(1000*log(prime)/log(10)). Adding up these logs and
comparing with some threshold LOG_LIM tells us if we found a number
with a lot of divisors in the factor base. Note that when we do find
one, we have all the divisors at hand so no trial division is necessary!
Thus this part is fast and we can afford to do it quite often.
Here is some more complete code. Note that as we traverse the list we
accumulate the sum of logs and also stash the indices in a little
table as we go so we can use them later (see below).
==============================================================================
u16 index, nextIndex, *next, *table, *indices;
u32 s, *logs, *step, tmp;
ulong i, j, k;
...
i = j = 0UL;
for (; ; ) {
index = table[j];
if (index) {
s = 0U;
table[j] = 0U;
k = 0UL;
do {
s += logs[index];
nextIndex = next[index];
tmp = (u32)j + step[index]; if (tmp >= LIM) tmp -= LIM;
next[index] = table[tmp];
table[tmp] = index;
indices[k] = index;
++k;
index = nextIndex;
} while (index);
if (s > LOG_LIM) { /* Candidate found (rare case). */
... PROCESS IT (SEE BELOW)...
} /* end if */
} /* end if */
++i; ++j; if (j == LIM) j = 0UL;
} /* end for */
==============================================================================
In the sieving we leave out the first few progressions with the
smallest steps, up to 100 say as Bob Silverman suggested for the
original sieve. When we divide out the factors we know from sieving
(they're between 100 and LIM) we will be left with a cofactor that has
some small primes less than 100 and a "large prime part" of primes
bigger than LIM (mostly: sometimes there is a sieving prime that
appeared to a large power).
If we choose the value of LOG_LIM so that the cofactor fits in 45 bits
or so, then we can find it quickly by multiplying by inverses of the
known factors using double-precision floating point. Alternatively we
can allow the cofactor to fit in 64 bits and find it by multiplying by
64-bit 2-adic inverses (if you don't know what those are, don't worry!)
Then after dividing out the small primes, we are left with the large
prime part and if it is below some limit LIM2 we report the number
along with the factorisation found. And we're done.
==============================================================================
u32 *smallPrimes;
u64 p, w, *inverses;
...
/* Divide out factors known from sieving. */
do {
--k;
w *= inverses[indices[k]];
} while (k);
/* Divide out small primes. */
for (k = 0UL; k < SMALL_PRIMES; ++k) {
p = smallPrimes[k];
while (w % p == 0UL) w /= p;
} /* end for */
/* Now w is the large prime part. */
if (w < LIM2) { /* Rare case. */
printf("Got one at i = %lu, large prime part = %lu\n", i, w);
... PROCESS IT...
} /* end if */
==============================================================================
NB: A faster way to divide out the small primes is to handle 2
separately and then handle the odd ones using a table like this:
----------------------------------------------------------------------------
static const u64 data[SMALL_PRIMES-1UL][2] = {
{ 12297829382473034411UL, 6148914691236517205UL } /* 3 */
, { 14757395258967641293UL, 3689348814741910323UL } /* 5 */
, { 7905747460161236407UL, 2635249153387078802UL } /* 7 */
...
};
----------------------------------------------------------------------------
The first term in each pair is the 2-adic inverse of the corresponding
odd prime and the second is a limit: floor(2^64/prime). Then it can be
shown that the prime divides some number n if and only if n*inv <= lim.
----------------------------------------------------------------------------
/* Divide out twos. */
while ((w & 1UL) == 0UL) w >>= 1;
/* Divide out odd small primes. */
for (k = 0UL; k < SMALL_PRIMES-1UL; ++k) {
u64 inv = data[k][0], lim = data[k][1], x;
while ((x = w*inv) <= lim) w = x;
} /* end for */
----------------------------------------------------------------------------
Bye,
Rob.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Stream Ciphers and Quantum Computer Resistance
Date: Sun, 02 May 1999 17:23:56 GMT
>There are really two pratical ways to solve this problem
> one is to use a true OTP ( One Time PAd) and the other is to use an
> extremly high entropy system such as scott19u.zip where one uses a long
> random file of ones choice and than a password to protect it. But even
> then to be safe one should every so often change the long random key
> file since if both the source code and long secrect key file is stolen
> a quantum compter could be used to guess what password was used but it
> is many orders of magnitude safer than any of the AES candidate types
> with there small NSA friendly type of key lengths. But the trick is
> to have the entropy high enough such that more than one solution exists
> that way a quantum computer could never settle down on the correct
> solution.
You have never proved that compression and encryption can go hand in hand to
make a safe cipher. You only conjectured that. In fact they are different
fields so I don't know where they come in together...
A real cryptosystem has a confusion sequence which hopefully is as random as
the key. That is all you need for a cryptosystem.
Tom
>
> David A. Scott
>
> --
> http://cryptography.org/cgi-bin/crypto.cgi/Misc/scott19u.zip
> http://members.xoom.com/ecil/index.htm
> NOTE EMAIL address is for SPAMERS
> to email me use address on WEB PAGE
>
> -----------== Posted via Deja News, The Discussion Network ==----------
> http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
>
--
PGP public keys. SPARE key is for daily work, WORK key is for
published work. The spare is at
'http://members.tripod.com/~tomstdenis/key_s.pgp'. Work key is at
'http://members.tripod.com/~tomstdenis/key.pgp'. Try SPARE first!
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] ()
Subject: How to Save MAGENTA
Date: 2 May 99 17:58:22 GMT
The f-function of MAGENTA is very impressive in appearance. But it does
indeed, as Bruce said, have a weakness. It has an awful lot of symmetry.
The basic unit of that f-function, repeated many times, is a
transformation involving two bytes, where each byte is replaced by itself
XOR the S-box entry indexed by the original value of the other byte. This
basic unit is non-invertible.
However, one could, with two table-lookups and two XORs, also do two
rounds of a mini-Feistel process. So, if one used some key bits to choose,
say during the second of the three large blocks of operations, between
these two possible actions in each position, one would have an f-function
that was more complex, and much harder to analyze.
John Savard
------------------------------
From: "Roger Schlafly" <[EMAIL PROTECTED]>
Subject: Re: Paper on 512 cracking
Date: Sun, 2 May 1999 11:08:05 -0700
UBCHI2 wrote in message <[EMAIL PROTECTED]>...
>Is it true that either Adelman or Shamir has recently written a theoretical
>paper on how to crack up 512? Is the method practicable if so?
http://www.nytimes.com/library/tech/99/05/biztech/articles/02encr.html
According to a story in today's NYTimes, Shamir is proposing a
machine which might make 512-bit vulnerable in the future a little
sooner.
http://www.nytimes.com/library/tech/99/05/biztech/articles/02encr.html
Israeli Scientist Reports Discovery of Advance in Code Breaking
By JOHN MARKOFF
An Israeli computer scientist is expected to shake up the world of
cryptography this week when he introduces a design for a device that could
quickly unscramble computer-generated codes that until now have been
considered secure enough for financial and government communications.
In a paper to be presented Tuesday in Prague, the computer scientist, Adi
Shamir, one of the world's foremost cryptographers, will describe a machine,
not yet built, that could vastly improve the ability of code breakers to
decipher codes thought to be unbreakable in practical terms. They are used
to protect everything from financial transactions on the Internet to account
balances stored in so-called smart cards.
Shamir's idea would combine existing technology into a special computer that
could be built for a reasonable cost, said several experts who have seen the
paper. It is scheduled to be presented at an annual meeting of the
International Association for Cryptographic Research, which begins on
Monday.
The name of Mr. Shamir, a computer scientist at Weizmann Institute of
Science in Rehovoth, Israel, is the "S" in R. S. A., the encryption design
that has become the international standard for secure transmissions. He is a
co-inventor of R.S.A. -- with Ronald Rivest of the Massachusetts Institute
of Technology and Leonard Adleman of the University of Southern California.
R.S.A. is known as public-key cryptography. In this system, a person has a
public key and a private key. The public key is used to scramble a message
and may be used by anyone, so it can, even should, be made public. But the
private key that is needed to unscramble the message must be kept secret by
the person who holds it.
R.S.A., like many public-key systems, is based on the fact that it is
immensely difficult and time-consuming for even the most powerful computers
to factor large numbers. But Mr. Shamir's machine would make factoring
numbers as long as about 150 digits much easier, thus making it much simpler
to reveal messages scrambled with public-key encryption methods.
A number of advances in factoring have been made in the last five years. But
most of them are the result of applying brute force to the problem.
When R.S.A. was created in 1977, Mr. Shamir and his colleagues challenged
anyone to break the code. Employing 1970's technology, they said, a
cryptographer would need 40 quadrillion years to factor a public key, and
they predicted that even with anticipated advances in computer science and
mathematics, no one would be able to break the code until well into the next
century.
In fact, a message the trio had encoded with a 129-digit key successfully
withstood attack for only 17 years. It was factored by an international team
of researchers in 1994.
Using Mr. Shamir's machine, cracking the 140-digit number would be reduced
to the difficulty of cracking a key about 80 digits long -- relatively easy
by today's standards.
Researchers said that if his machine worked it would mean that cryptographic
systems with keys of 512 bits or less -- that is, keys less than about 150
digits long -- would be vulnerable in the future, an exposure that would
have seemed unthinkable only five years ago. The longer 1,024-bit keys that
are available today would not be vulnerable at present.
------------------------------
From: Terje Mathisen <[EMAIL PROTECTED]>
Subject: Re: Factoring breakthrough?
Date: Sun, 02 May 1999 21:29:57 +0200
Robert Harley wrote:
>
> lcs Mixmaster Remailer <[EMAIL PROTECTED]> writes:
> > Rumor has it Adi Shamir will announce factoring breakthrough soon.
> > Increasing efficiency by orders of magnitude and breaking keys 100-200
> > bits longer than current state of the art.
> >
> > Anybody confirm/deny?
>
> I've no idea, but this reminded me of an implementation trick which
> seems to be useful yet not widely known (at least I don't recall
> having seen it written down).
>
> It's how to do sieving in a cache-friendly way.
>
> The way of sieving that everyone has been using for 10 or 15 years
> doesn't take cache effects into account at all. As the speed of chips
> continues to increase faster than the latency of main memory, a
> cache-friendly method is bound to become more widespread eventually!
Actually Rob, this has already happened, AFAIK.
My own toy sieve code uses just 128 KB of table space, reusing the same
block for each new area to be searched.
Dan J Bernstein (sp?) has posted a msg about his implementation which is
6 times faster than my code, IMHO there's no way he could have done that
without thinnking a lot about cache effects.
Terje
--
- <[EMAIL PROTECTED]>
Using self-discipline, see http://www.eiffel.com/discipline
"almost all programming can be viewed as an exercise in caching"
------------------------------
From: "hapticz" <[EMAIL PROTECTED]>
Subject: Re: Deadly threats
Date: Sun, 2 May 1999 15:14:09 -0400
hey, nobody's gonna steal my ideas!
--
best regards
[EMAIL PROTECTED]
remove first "email" from address, sorry i had to do this!
SCOTT19U.ZIP_GUY wrote in message <7ghmhe$sss$[EMAIL PROTECTED]>...
|In article <[EMAIL PROTECTED]>,
| Anonymous <[EMAIL PROTECTED]> wrote:
|> hapticz wrote:
|> > if I continue to send deadly physical threats to high government
officials
|> > in encrypted form without the keys, am i liable to be prosecuted?
|>
|> 0000000 302 135 335 270 135 221 156 331 336 111 271 200 366 332 266 257
|> 0000010 166 374 342 035 351 376 064 144 362 166 366 103 231 033 016 101
|> 0000020 177 017 054 335 243 042 116 236 120 277 250 146 142 222 242 041
|> 0000030 332 366 321 067 043 133 064 117 324 141 206 012 366 146 062 355
|> 0000040 212 143 164 332 303 006 236 320 026 271 132 330 043 241 117 272
|> 0000050 340 211 166 164 175 164 020 370 230 372 270 252 276 050 247 277
|> 0000060 140 310 021 057 323 117 303 332 131 326 116 101 347 333 200 305
|> 0000070 246 176 141 327 315 243 305 334 222 262 050 010 106 126 127 340
|> 0000080 351 232 121 026 125 001 266 064 370 161 377 152 000 224 202 304
|> 0000090 112 022 114 176 312 113 154 327 112 332 025 211 222 021 337 266
|> 00000a0 106 274 050 357 154 134 142 365 377 143 107 316 320 117 210 063
|> 00000b0 333 027 244 042 317 060 322 267 367 377 343 377 162 270 064 307
|> 00000c0 066 102 365 226 347 242 106 372 022 023 316 241 033 237 275 351
|> 00000d0 163 062 022 305 271 373 005 140 153 134 144 064 013 044 222 366
|>
|>
|
| If you trying to imply this is some secret threat. The NSA can easly
|find out how the messages get sent. There is no real why to hid the acount
|and the telephone one used to send the message. Unless you do it from
|someones elses house. Or an internet cafe.
|
|David Scott
|
|--
|http://cryptography.org/cgi-bin/crypto.cgi/Misc/scott19u.zip
|http://members.xoom.com/ecil/index.htm
|NOTE EMAIL address is for SPAMERS
|to email me use address on WEB PAGE
|
|-----------== Posted via Deja News, The Discussion Network ==----------
|http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
