Cryptography-Digest Digest #661, Volume #9 Fri, 4 Jun 99 22:13:02 EDT
Contents:
Re: evolving round keys
Re: Challenge to SCOTT19U.ZIP_GUY ([EMAIL PROTECTED])
Re: Challenge to SCOTT19U.ZIP_GUY (Tim Redburn)
Re: Another source of random numbers ([EMAIL PROTECTED])
Re: Cryptography CENSORED on web site? ("rosi")
Re: random numbers in ml (fungus)
Re: what cipher? (better description) ([EMAIL PROTECTED])
Re: PGP probability of choosing primes? (Geoff Thorpe)
Re: Challenge to SCOTT19U.ZIP_GUY (SCOTT19U.ZIP_GUY)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: evolving round keys
Date: 5 Jun 99 00:21:06 GMT
[EMAIL PROTECTED] wrote:
: I was just wondering why block ciphers have keys which remain
: constant? Would there be any benefit of having post/pre white keys
: that change per block (with a cycle length of the 2^n where n is the
: number of bits per word).
Actually, that is quite beneficial in terms of security.
However, despite that, all block ciphers will still have keys that are
constant.
Why is that? Is that because the cryptographic community obstinately
ignores a good way to make better ciphers? No, it's because if the round
keys change from block to block, you have a stream cipher ... it isn't
called a block cipher anymore.
Since most stream ciphers involve a pure XOR of a pseudo-random bit stream
to the plaintext, it would be nice to have a term for that kind of cipher
- say, a "pure" stream cipher - so that a cipher which combines
encipherment on larger blocks with an ever-changing element in the cipher
could be distinguished.
John Savard
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Challenge to SCOTT19U.ZIP_GUY
Date: Fri, 04 Jun 1999 23:55:10 GMT
> Actually scott19u is highly modularized that is why I have so many
> macros.
#define QR +
#define YI (
#define GJ )
#define WX =
A WX A QR YI 5 QR B GJ;
Point made and set.
Tom
--
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!
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (Tim Redburn)
Subject: Re: Challenge to SCOTT19U.ZIP_GUY
Date: Fri, 04 Jun 1999 23:58:58 GMT
On Fri, 04 Jun 1999 20:24:05 GMT, [EMAIL PROTECTED]
(SCOTT19U.ZIP_GUY) wrote:
>
> I have worked on many aircraft simulations and OFP;s one of the main
>problems that seems to occur over and over is that other people keep
>missing the obvious errors in the code becasue most people inheirently
>put faith on the comments and this leads to major maistakes that take
>years to find and fix.
Quite the opposite. Comments tell you what the programmer intended.
It is then easier then to verify that the code actually works
as intended. If you don't know what the code was meant to do, how can
you debug it ?
- Tim.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Another source of random numbers
Date: Sat, 05 Jun 1999 00:38:34 GMT
<snip>
This may not be not what you are looking for but...
Irrational numbers like the truncated fraction of root(2), are used
because they have better xor weights (hamming distance) when used in
conjuction with other irrational numbers. They can be used in key
scheduling where multiples of the irrational (see RC5, RC6, TEA for
example) are used. If the number is odd, then it's arithematic series
is of maximal length, which is a usefull property.
Generally picking random constants (like 0x80202080) are bad because
they have bad xor profiles (the adjacent numbers in the sequence). The
first four numbers (using 0x9E3778B9) are
0x9E3779B9 -> 10011110001101110111100110111001
0x3C6EF372 -> 00111100011011101111001101110010
0xDAA66D2B -> 11011010101001100110110100101011
0x5384540F -> 01010011100001000101010000001111
As one can see in the first four outputs is that each bit is not
equally distributed. However since the series is maximal length one
could prove that all bit states (1 or 0) are equally probable. Of
course other numbers are possible.
I hope that sheds some light...
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: "rosi" <[EMAIL PROTECTED]>
Subject: Re: Cryptography CENSORED on web site?
Date: Fri, 4 Jun 1999 20:41:27 -0400
Dear John,
I do not think people will have the 'suppressing' notion at all.
You are right. It is not unimportant to talk about IT. It is my opinion
that IT needs
to be talked about in the 'right' context. Actually, it is important to talk
about it AS
IT IS.
(Don't like to sound cryptic, though)
--- (My Signature)
John Savard wrote in message <[EMAIL PROTECTED]>...
>Mok-Kong Shen <[EMAIL PROTECTED]> wrote, in part:
>
>>Perhaps my English knowledge is not good engough, but I don't
>>clearly (unambigiously) understand what you wrote. However, your
>>title line suggested that someone has illegally modified your
>>HTML file.
>
>No, I didn't mean that at all, although I intended to use a wording
>that - humorously - suggested such thoughts or others. Rather, as the
>text of the post should make clear, I meant that I had, in writing my
>site, omitted mentioning the OTP...
>
>but I had done so so thoroughly, that it might seem _I_ was engaging
>in censorship, trying to suppress all knowledge of the existence of
>the OTP!
>
>John Savard ( teneerf<- )
>http://members.xoom.com/quadibloc/index.html
------------------------------
From: fungus <[EMAIL PROTECTED]>
Crossposted-To: comp.sys.cbm,comp.sys.apple2.programmer
Subject: Re: random numbers in ml
Date: Sat, 05 Jun 1999 01:19:21 -0100
Matthew Montchalin wrote:
>
> At least with the Commodore, there just wasn't that much
> real estate left in zero page to put aside for use as counters
> ('virtual' shift registers, for instance) for the random number
> generator...
>
The Commodore 64 had a built in hardware random number generator.
The MIB are trying to control something that was massively exported
in the 80's.
--
<\___/>
/ O O \
\_____/ FTB.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: what cipher? (better description)
Date: Sat, 05 Jun 1999 00:42:32 GMT
> I wonder; it said that I can use 16x16 to encrypt a 16bit value
> at a time... (instead of an 8-bit one), but can't I do the 16x16 on
> the 8-bit level as well... ie: instead of having 256 values in the
> array, each from 0-256, I'll have 0xFFFF values each from
> 0-256... (seems to make it much stronger...)
>
It will not work (as described) with 2^8 permutations of numbers from GF
(2^8). This is because the random offsets are only 8 bits. So you
would not be able to effective mix the entire array. Also only 8 bits
of 'entropy' are avail per sbox entry so some tricks would be required
to use larger tables.
> btw: how important to security that swap of values in the array,
> it would be nice if I could avoid it... (that would mean I can
> seek to specific locations in the file without looping for a while
> to synch the array with the counter)
Without the swap it has much shorter cycle length (probably around 2^16
at the most, which is the 2^8 permutations of x, and 2^8 of y).
Either use the standard RC4 with 8 bit entries or 16 bit, but keep the
swap, and proportial table sizes.
Tom
--
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!
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Geoff Thorpe <[EMAIL PROTECTED]>
Subject: Re: PGP probability of choosing primes?
Date: Fri, 04 Jun 1999 21:50:49 -0400
Hi there,
Bob Silverman wrote:
>
> In article <[EMAIL PROTECTED]>,
> Geoff Thorpe <[EMAIL PROTECTED]> wrote:
> > > In article <7iq213$k7$[EMAIL PROTECTED]>,
> The upshot of that work was that there are
> > theoretical results which say it is not that "critical" a problem. Ie
> > the entropy arguments say (in my words, not the author's) that the
> > entropy in sequential primality searching for primes of size "x" bits
> > equivalent to the entropy in a true random primality search for primes
> > of size "y" bits where I think y was x*2/3
>
> This should be x^(2/3)....
Umm ... like I said, it's from memory - but "x" was the number of bits
in the range being discussed, so we're talking an exponent here, hence I
think (x*2/3) is the number of bits, but I'll defer to you as you're
obviously pretty familiar with stuff I read passingly quite a while
back. Can you recall where that comes from, I'd be interested to do a
re-read, especially if it's published online.
> ... this is from the deep
> > recesses of my memory so I could be WAAAY off here.
>
> Actually, it is fairly easy to show that the entropy must be a
> fractional power of x, but AFAIK, the exact power is not known.
Quite possible, I recall that what I read spoke of bounds, nothing
exact.
> > I'm not so sure ... I'm pretty sure I agree that there's no conclusive
> > result that answers all the questions, but I think there was some work
> > done on the probability distribution of "gaps" ... the mean of which
> > as you say, about log(L/2).
>
> Actually, it is the case that not only do we not have a PROOF, but that
> the distribution is NOT known. Cramer's conjecture states, for example,
> that there is always a prime between x and x + (log x)^2. Recent
> work by Hildebrand and Maier on the distribution of primes in short
> intervals suggests that Cramer's conjecture MAY be false. But noone
> really knows. The true answer might be x + (log x)^(2 + epsilon)
> for any epsilon > 0, or it might be x + (log x)^2(loglog x) or
> Cramer's conjecture might be true. The exact answer isn't KNOWN.
Well I'm forced to bite my lip because on the one hand you obviously are
familiar with the background on this stuff, but I have a nagging
recollection that the entropy argument by which the "2/3-result" was
derived was based on distribution arguments, albeit that they may well
have been of a probabilistic nature.
> there is no reason to believe that if p and p + k are prime and
> k is small relative to p that either p-1 or p+k-1 should be more
> smooth than randomly chosen odd numbers of the same size.
Yep, and like you explained very well - factorisation is not likely to
leap forward in any noticable way if it thinks there's a better than
even chance the primes it's looking for were at the back end of a
sequential search.
> > As it turns out, I came up with a workaround for this
>
> Does the workaround extend to finding primes in an A.P? Sometimes
> one wants to restrict to finding primes p such that p-1 and p+1
> have particular prime factors. This means a sequential search
> over primes in the A.P. such that p = 1 mod p1 and p = -1 mod p2.
The workaround was pretty simple - it took an awfully big sequence of
odd numbers following a randomly chosen start point, and using some
bit-twiddles could perform a low-prime sieve on all of them at a
slightly higher cost than performing a low-prime sieve of just one. Then
one uses a cryptographic primitive of some kind (Peter came up with this
bit so I can't tell you what he was using) to ensure that you jump
around in your block looking for odd numbers that passed the low-prime
sieve in a "random" way ... the benefit of this method is that if you
started your block one odd number "to the right", then all the
odd-numbers common to the overlap of both blocks get examined in a
completely different order. It's not brain surgery at all ... there were
however some interesting possibilities for "optimisations", but quick
examinations showed they would actually take longer than just going
through this wholesale just as is using.
The obvious "problem" with the technique is that in some sense the
problem still exists: this now gives a higher probability of discovery
to primes that lie in "sparse" zones than to those that lie in "dense"
zones, eg. compare a block that contains 2 primes to a block that
contains 10. However, the gut feeling I had here is that it is "less
likely" that primes lying in blocks containing less primes than expected
satisfy "special properties", than for primes that by themselves have an
abnormal string of leading non-primes. Hand-waving abounds, and nothing
of rigourous theoretical value to demonstrate, in case it occurs to you
to ask.
For a non-number-theorist, is A.P.=Arithmetic Progression? If so, yes it
should adapt to those quite nicely.
> >I don't think
> > anybody knows if this issue is a big deal at all, even the known
> entropy
> > loss is not disastrous
>
> As I said, it is TINY. (a fractional power of x is small relative
> to x for x in the range being considered [512 bits]). If the exponent
> is (2/3), then the loss in entropy is 2^(2/3 * 512)/2^512 i.e.
> about 1 part in 2^170.
Well I'm more interested in probabilities, and if the expected
distribution of "gaps" (ok, I guess I mean "give me a prime - now how
far is it to the next one?"). It seems to me that the "bias" here is
directly related to how non-thin the probability distribution is of that
"gap" variable ... an aesthetic "feel" I have is that it would be
something like a Poisson distribution, ie. can be anything from "right
next door" (a prime-pair) up to some theoretical limit well in excess of
log(L/2). If it was anything like this (I guess the standard deviation
of the gap is the relevant measure here) then the bias seems non-trivial
to me. If primes with big gaps ahead of them have "properties", and 5%
of primes have such gaps (perhaps giving them an uneven, perhaps 30%,
chance of discovery) then that would be significant.
> > Nope, it's definately been quantified using an entropy argument,
>
> But saying that the entropy reduction is (say) O(x^2/3) really
> doesn't measure it exactly, except to verify that it is indeed tiny.
OK, perhaps the entropy measurement yes - but if you disregard the issue
of direct improvements in factoring (which we both think to be doomed to
nill), the bias towards primes with big gaps in front of them is
non-negligible, and if such primes occur in noticable enough quantities
in the expected distribution of "gaps" then the bias is no longer
"tiny". If someone could actually produce a modelled probability
distribution of "gaps" (say based on data sampled from 512-bit primes
starting with the hex "800...") then we could perhaps discuss this more
meaningfully - but I'm packing and changing countries tomorrow night so
that's not going to be me, at least for now!
> > That depends on the distribution of the gaps ... I think it's more
> than
> > you think - Log(L/2) is just the mean, there's no reason the
> > distribution should be "thin".
>
> Gaps are bounded by [2, (log L)^k] for some k. It is known
> that small gaps have density zero. However, the density of gaps
> of the size (log L)^delta for delta < 1 is not known. It is
> known that the density of gaps which are bounded by C log L is 1.
> (PNT would be false otherwise).
Hmm ... ok, but I still feel a bit queezy about something - even if only
2% of primes fall at the end of what we might define an "abnormal"
string of non-primes - if that length of non-primes we've just defined
is substantially longer than the mean, then the impact on sequential
searches for primes IS significant. Like I said in my first post - if it
turns out that those "abnormal" primes also have special properties then
PGP2.6 users might want to take a closer look. If we do real random
searches for primes, then that 2% stays as 2% and the bias shouldn't be
an issue anymore.
> > have "big gaps" in front of them. What I AM a little worried about is
> > that primes that have extremely abnormal length blocks of non-primes
> in
> > front of them, exhibit desirable (for the cryptanalyst) properties.
>
> What are those properties??? Please specify.
ok my apologies for poor wording - I was worried that there MIGHT be
such properties, not that there are. But the possibility is not
inconceivable, as I hope you agree.
> > Nobody has managed (as far as I know) to put a non-trivial upper-bound
> > on the size of "gaps" for numbers of "x" bits,
>
> False. It is fully proven that there is always a prime between
> x and x + x^(11/20 + eps). GRH would lower this to x + x^1/2 log x.
I said non-trivial ... of course it's easy to put trivial bounds in
place, even constructively ... but as far as the distribution of "gaps"
goes - you can go quite a bit beyond the mean gap size before you hit
either of those bounds (unless my mental calculation skills have fallen
away a lot faster than I'd realised), ie. it's still possible to have
really "abnormal" primes (to continue my terrible terminology) before
those bounds clip them off.
> Even if Cramer's conjecture is a little bit wrong, there is
> certainly always a prime between x and x + (log x)^k for some
> reasonably small k (even though a proof is lacking and we don't
> know the true value of k)
This still allows a REALLY non-thin distribution.
> so it's possible that
> > there's a large number (proportionally) of primes out there with
> REALLY
> > BIG gaps in front of them.
>
> No. This would make PNT false. The set of primes preceded by very
> large gaps must have density 0 for PNT to be true.
I'm from a different field so you might have to clarify what density
means in this context. But a simple "bell-curve" type illustration
should show that even if only a small quantity of primes fell at the end
of a reasonably large gap - the bias for *sequential searches* can be
significant. The original poster was (as was I) interested in sequential
searches and possible problems thereof. If 5% of the primes have gaps in
front of them more than 5 times the mean gap, and such primes exhibit
"properties" - then a significant bias of sequential-search generated
primes exhibit the properties (considerably more than 5%).
> >This makes them (a) likely to turn up in
> > people's keys with a much higher probability than perhaps they should,
>
> Impossible on PNT
Could you explain why - like I said in my last paragraph - if they
should be turning up 5% of the time but are turning up say 25% or more
of the time (because they're more prone to a sequential search than
their counterparts) then this is significant.
> > and (b) dangerous if they exhibit special properties
>
> What are these properties to which you refer? One property
> (smoothness of p-1 or p+1) is no more likely than for uniformly
> random integers.
Like I said, I did not know of properties these primes exhibit, only the
simple fact that they may well exhibit properties, for better or worse,
as the theory develops. Sequential searches give them a better than fair
chance of turning up in your RSA keys (among any others) - is this good?
> > 5, 11 & 13, 17 & 19, 29 & 31, etc). Considering the opposite
> properties,
> > namely where there is a large block of sequential odd numbers that are
> > NOT prime would seem to me just as worth-while
>
> It HAS been considered. The work on Cramer's conjecture is just this.
OK - you're better aquainted with the area than I - do you know if
there's anything interesting about primes lying at the end of an
abnormal string of non-primes? What do you feel is the likelihood that
they might?
> > Or get a surprise visit from the NSA [;-)
>
> Please. Even with the smiley, comments like that have no place
> in a discussion such as this.
Well - you'd just suggested the original poster could win the Fields
Medal in reposte-like fashion, my "joke" was in the same vein ... take
it easy - I'm genuinely interested in what other's have to say about
this as I know enough to care about the question, but not enough to
provide any kind of definitive answers. If you think I'm brainless
enough to make a comment like that in any way EXCEPT a flippant offhand
joke then you do me little credit.
Perchance, if you reply to this post - please email it to me personally
too because I'm in relocation for the next few days at least.
Cheers,
Geoff
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Challenge to SCOTT19U.ZIP_GUY
Date: Sat, 05 Jun 1999 02:54:44 GMT
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Tim
Redburn) wrote:
>On Fri, 04 Jun 1999 20:24:05 GMT, [EMAIL PROTECTED]
>(SCOTT19U.ZIP_GUY) wrote:
>
>
>>
>> I have worked on many aircraft simulations and OFP;s one of the main
>>problems that seems to occur over and over is that other people keep
>>missing the obvious errors in the code becasue most people inheirently
>>put faith on the comments and this leads to major maistakes that take
>>years to find and fix.
>
>Quite the opposite. Comments tell you what the programmer intended.
>It is then easier then to verify that the code actually works
>as intended. If you don't know what the code was meant to do, how can
>you debug it ?
>
>
>- Tim.
Comments that tell what the input and output are can help but the
rest usually just cluters the stuff up.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
http://members.xoom.com/ecil/index.htm
NOTE EMAIL address is for SPAMERS
------------------------------
** 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
******************************
