Cryptography-Digest Digest #521, Volume #11 Sun, 9 Apr 00 22:13:00 EDT
Contents:
Re: Encryption in Software... (Kent Briggs)
Re: Blowfish constants (Tom St Denis)
Re: A question on Time-Locking. (David A. Wagner)
Re: OAP-L3: Semester 1 / Class #1 All are invited. (DMc)
Hash function based on permutation polynomials (Tom St Denis)
Re: Keeping numbers small in RSA ([EMAIL PROTECTED])
Re: GSM A5/1 Encryption (Guy Macon)
Re: Blowfish constants (Boris Kazak)
Re: Blowfish constants (Tom St Denis)
Re: Mersenne RNG, RNG questions (Tim Tyler)
Re: Skipjack algorithm.
Re: Blowfish constants (stanislav shalunov)
----------------------------------------------------------------------------
From: Kent Briggs <[EMAIL PROTECTED]>
Subject: Re: Encryption in Software...
Date: Sun, 09 Apr 2000 23:09:56 GMT
Simon Johnson wrote:
> Hasn't the export restriction been lifted?
>
> Or is that on Two_Fish?
The U.S. export restrictions were loosened considerable in January but
exported software over 64 bits in strength still requires a blessing
from the BXA.
--
Kent Briggs, [EMAIL PROTECTED]
Briggs Softworks, http://www.briggsoft.com
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Blowfish constants
Date: Sun, 09 Apr 2000 23:39:10 GMT
lordcow77 wrote:
>
> In article <[EMAIL PROTECTED]>, Tom St Denis
> <[EMAIL PROTECTED]> wrote:
> >Do the constants in blowfish [for the sbox/pbox] have to be
> pi? Can
> >they just be sum(0, 1024, C) where 'C' is some odd constant?
> That would
> >space some space in the library...
> >
>
> Why do you insist on inventing your own notation for some very
> simple concepts? "sum(0, 1024, C)" has absolutely no standard
> meaning at all. It's possible to guess from context that you
> mean incrementing each successive S-box entry by some constant,
> but why can't you just say that? Similarly, why do you always
> refer to the construction of the PRNG described in Knuth's TAOCP
> as Alg. M? "Alg. M" means nothing except in context, and if you
> provide the context, why can't you just use a more descriptive
> name? Taking the "dot product" of two numbers, as you suggested
> in a previous posting, also has no well-defined, standard
> mathematical meaning; taking the dot product of two numbers
> interpreted as bit vectors makes more sense, but again, why
> don't you just say what you mean instead of saying what you
> think other people say when they mean what you mean?
I just meant to add like so
S[0] = C1
for i = 1 to N do
S[i] = S[0] + C2
Sorry if that's too complex.
Similarly Alg.M is defined both in Applied Crypto and in Knuth. It's
well known I would think. When I said the dot-product of two numbers,
while technically inccorect was based on the asumption your number is
just a vector components. It's actually defined in Knuth as x^2 <dot> Z
mod n. I can get the page ref if you want [near page 40 or so].
If you have a problem with my ideas just ask instead of being critical.
Tom
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: A question on Time-Locking.
Date: 9 Apr 2000 16:01:32 -0700
In article <8cqous$oah$[EMAIL PROTECTED]>,
Simon Johnson <[EMAIL PROTECTED]> wrote:
> Is there anyway to make a cipher such that no matter how much computing
> power u threw at the problem, it would always take the same amount of time
> to solve.
Does the following paper help with the application you had in mind?
``Time-lock puzzles and timed-release Crypto.''
Ronald Rivest, Adi Shamir, and David Wagner.
http://www.cs.berkeley.edu/~daw/papers/timelock.ps
------------------------------
From: DMc <[EMAIL PROTECTED]>
Subject: Re: OAP-L3: Semester 1 / Class #1 All are invited.
Date: Sun, 09 Apr 2000 23:47:33 GMT
> >>>On Tue, 04 Apr 2000 16:03:15 -0700, lordcow77
> >>><[EMAIL PROTECTED]> wrote:
>
> >>>Not true; the nth iterate of a LCG can be calculated based
> >>>solely on the seed value to the generator. Hint: think modular
> >>>exponentiation.
> >>>
> >> [EMAIL PROTECTED] answered:
> >>
> >>This is the stuff that makes me crazy. Do what you say you can
> >>do and maybe I will understand. An engineer made the same claim
> >>in a magazine article several years ago, and he was not even
> >>close.
> >
> > lordcow77 answered:
> >
> >It's proven in _Seminumerical Algorithms_.
> >
> dmc0006@home answered:
>
> Is this "The Art of Computer Programming, Volume 2, Seminumerical
> Algorithms" 1st, 2nd, or 3rd Edition by any chance? I have the 3rd.
> Give me the page number(s) for this proof. I am VERY familiar with
> pages 1 -> 193 in this book.
On Sat, 8 Apr 2000 07:52:43 -0700, "Scott Fluhrer"
<[EMAIL PROTECTED]> wrote:
In the first edition, the method is listed as equation 3.2.1(6).
Actually proving it is an exercise - 3.2.1(4) (the answer in the back
just says "Induction on k"
--
poncho
--
Thank you Poncho. It is in the 3rd edition also.
Lordcow77 says "the nth iterate of a LCG can be calculated based
solely on the seed value to the generator." I gave A.S.S. a seed value
of 1 (one). So I invite lordcow77, or anyone else, to "modular
exponentiate" this particular seed value "solely" and arrive at any
sort of sensible result.
I passed this formula by a long time ago. It is one of those things
that is good theory, but of little practical use. It can only be
calculated with a severely limited set of "k" values.
For instance, the original problem I gave A.S.S requires calculating
16 807 ^ 1 073 741 824. That calculation result is way beyond the
limits of an "infinite" digits program I have. I leave myself open to
the possibility of a program somewhere which can handle such a
calculation. But realize, we are only discussing an exponentiation
halfway through a trivial length number set {1 -> 2 147 483 646}.
Now that I look at it again, I realize it is just another reason why
the spectral test as interpreted by Knuth's anonymous author is
probably invalid.
[EMAIL PROTECTED]
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Hash function based on permutation polynomials
Date: Sun, 09 Apr 2000 23:57:13 GMT
Still having fun with permutation polynomials [mod 2^w] I designed a
192-bit hash compression function. It's designed like a
balanced-feistel function instead of the typical unbalanced target heavy
hashes.
It's not at all fast, but it's compact and takes little ram. And of
course on todays desktops it's not bad for hashing messages <1mb.
If anyone wants to check it out [should compile on any long=32bit
platform] it's in source form at
http://24.42.86.123/hash.c
It's just an idea in progress so it's not at all formal.
Another nice thing about my construction is that I can extend it easily
to other output sizes, like 256 bits.
Tom
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Keeping numbers small in RSA
Date: Sun, 09 Apr 2000 23:57:12 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> [EMAIL PROTECTED] wrote:
>
> > I am having some trouble calculating result = A*B mod n as part of a
> > modular exponentiation. The tempory value for A*B gets too big too
> > store before the modular reduction. I am limited to 32 bit storage
for
> > the tempory register.
>
> How do you calculate x^y? By reducing it to accumulating products (of
just
> two terms) (writing y in a binary expansion).
>
> How do you calculate x*y? By reducing it to accumulating sums (write
y in
> binary, say). This reduces the product to SUMS ... however!
>
> How do you do A+B mod n (if n fits in your word size, but 2n doesn't!
then
> A+B might be too large! Even ADDING, let alone multiplying, may
> overflow! To avoid that...
>
> Assuming A,B,n positive and all fit .. A,B<n,
> use:
>
> IF A>=N-B THEN SUM=A-(N-B)
> ELSE SUM=A+B)
>
> For doing the calculations, here it is in QBasic (something I wrote
up the
> last time this came up and the question poser did not want to use a
larger
> integer package). You would have to convert this to whatever language
you
> are using.
> ---------------
>
> The following QBasic routine calculates a^b mod n (a between 0 and n
> where a,b,n>0) without using any results larger than n.
>
> It uses the trick of expanding b=SUM[e_j*2^j] and using:
>
> answer=1:j=0:x=a
> LOOP through bits of b
> if e_j=1 then answer=(answer*x) mod n
> x=x*x mod n:j=j+1
> (answer is then a^b mod n)
>
> To do the multiplications mod n (for answer*x and x*x mod n) one uses:
>
> To calculate A*B mod n
>
> B=sum[f_j*2^j]
> PROD=0:j=0:x=A
> LOOP through bits of B
> if f_j=1 then PROD=(PROD+x) mod n
> x=(x+x) mod n:j=j+1
> (PROD is then A*B mod n)
>
> Having reduced everything to adding A+B mod n, one does that
calculation
> by:
>
> if A>=(n-B) then SUM=A-(n-B) else SUM=A+B
> (sum is then A+B mod n)
>
> which has no intermediate value which is negative (works for unsigned
> integers) and which leads to no term larger than n.
>
> -=-=-=-=-=- PROGRAMME -=-=-=-=-=-
> DECLARE FUNCTION add& (a&, b&, n&)
> DECLARE FUNCTION mult& (a&, b&, n&)
> DECLARE FUNCTION modpow& (a&, d&, n&)
>
> ' Calculates a^d mod n without intermediate results larger than n
> ' a,d,n>0
> ' QBasic: '=REMark, \=Integer division, &=Long Integer
> ' 19 February 2000: John McGowan
>
> CLS
> PRINT : PRINT "This calculates a^d mod n for long integers."
> PRINT : PRINT
> INPUT "a (number to be raised to power)"; a&
> INPUT "d (exponent = power)"; d&
> INPUT "n (modulus)"; n&
> a& = a& MOD n&
> IF a& < 0 THEN a& = a& + n&
> PRINT : PRINT
> PRINT "a^d mod n="; modpow&(a&, d&, n&)
>
> FUNCTION add& (a&, b&, n&)
> ' a,b,n>0: a and b both between 0 and n
> ' Adds a+b mod n without intermediate results larger than n
> ' Returns non-negative result
>
> IF a& >= (n& - b&) THEN add& = a& - (n& - b&) ELSE add& = a& + b&
>
> END FUNCTION
>
> FUNCTION modpow& (a&, d&, n&)
> ' a^d mod n (a,d,n>0)
> ' a between 0 and n
>
> pow& = 1: powsq& = a&: expo& = d&
>
> DO WHILE expo& <> 0
> IF (expo& MOD 2&) <> 0 THEN pow& = mult&(pow&, powsq&, n&)
> powsq& = mult&(powsq&, powsq&, n&): expo& = expo& \ 2&
> LOOP
>
> modpow& = pow&
> END FUNCTION
>
> FUNCTION mult& (a&, b&, n&)
> ' a,b,n>0 (a,b between 0 and n)
> ' multiplies ab mod n without intermediate results larger than n
>
> factor& = b&: prod& = 0&: temp& = a&
>
> DO WHILE factor& <> 0
> IF (factor& MOD 2&) <> 0 THEN prod& = add&(prod&, temp&, n&)
> temp& = add&(temp&, temp&, n&): factor& = factor& \ 2
> LOOP
>
> mult& = prod&
> END FUNCTION
>
>
Thanks for the info, I'll give it a whirl. Just for information, I am
using Delphi to implement a simple RSA demonstator. Due to this I do
not have to worry about security. I just need to be able to compute
the A*B mod n as stated. Ideally I want to be able to work with
arbitary length strings of numbers, converting to integers only for
calculations and keeping any calc results less than 32 bit in length.
Rick
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: GSM A5/1 Encryption
Date: 09 Apr 2000 20:11:50 EDT
In article <8cqsgp$lc6$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (David A. Wagner) wrote:
>
>In article <8cqqbl$[EMAIL PROTECTED]>,
>Guy Macon <[EMAIL PROTECTED]> wrote:
>
>> What I suggested was to add a random number of random characters at the
>> beginning and end of the plaintext before encrypting it.
>
>In the context of GSM, this requires you to add to the frame length, no?
I do not know, having no experience or training in GSM, and very little
in the field of cryptography. I am going by your words, on the reasonable
assumption that you know more about the subject than I do. Here is what
I have read so far (all direct quotes);
"Typically, the other is expensive [*] and tricky and require extensive
changes to the entire rest of the system. (avoiding known plaintext)"
"Footnote [*]: Your claims notwithstanding, adding to the length of
the GSM frame is very costly, because it imposes a huge overhead
(in bandwidth)"
Let's look at this in a logical fashion. All I advocated was padding
the plaintext by a couple of percent with random data at the beginning
and ending. If encrypting a plaintext plus some random data adds to the
length of the GSM frame, then encrypting a slightly longer plaintext
in the first place would also add to the length of the GSM frame. If
adding to the length of the GSM frame is very costly and imposes a
huge overhead in bandwidth, then GSM would seem to be a poor choice
for encrypting messages over a certain size. These are logical
conclusions that even a clueless newbie such as myself can come to
without any special knowledge or training. Assuming that your claim
about small increases of plaintext size causing "a huge overhead in
bandwidth" (a proposition that I lack the training to comment on) then
I must ask if this is a general property of other encryption schemes.
So far I have run experiments on PGP, OTP, and Ciphersaber on my computer
and have seen no such effect. Certainly you could not reasonably expect
me to know that small increases of plaintext size cause a huge overhead
in bandwidth. How would I know such a thing? Isd it even true? If so,
I would also point out that I never wrote a word that implied in any way
that I was discussing GSM in particular instead of cyphers in general.
Thus I repeat my valid request that you please refrain from putting
claims in my mouth that I never expressed, as you did when you wrote
"Your claims notwithstanding, adding to the length of the GSM frame is
very costly". I made no such claim. and I expect you to behave like a
gentleman and apologize for saying that I did.
------------------------------
From: Boris Kazak <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Blowfish constants
Date: Mon, 10 Apr 2000 00:37:12 GMT
Tom St Denis wrote:
>
> Do the constants in blowfish [for the sbox/pbox] have to be pi? Can
> they just be sum(0, 1024, C) where 'C' is some odd constant? That would
> space some space in the library...
>
> Tom
=======================
You can use anything as initial value for the sbox/pbox. The consequence
will be that Blowfish would initialize to different sbox/pbox setup,
depending on these initial values, and all test vectors that were so
carefully computed for "standard" implementation, will suddenly
become unusable.
Additionally, your correspondent must initialize Blowfish with exactly
the same initial values as you do.
If you wish to try, I can E-Mail you files where some popular constants
have been computed up to 16384 hex places. There are files for "e",
ln(2),
sin(1), sqrt(2) and several others. Have fun, initialize Blowfish in any
of alternative ways...
Best wishes BNK
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Blowfish constants
Date: Mon, 10 Apr 2000 01:12:12 GMT
Boris Kazak wrote:
>
> Tom St Denis wrote:
> >
> > Do the constants in blowfish [for the sbox/pbox] have to be pi? Can
> > they just be sum(0, 1024, C) where 'C' is some odd constant? That would
> > space some space in the library...
> >
> > Tom
> -----------------------
> You can use anything as initial value for the sbox/pbox. The consequence
> will be that Blowfish would initialize to different sbox/pbox setup,
> depending on these initial values, and all test vectors that were so
> carefully computed for "standard" implementation, will suddenly
> become unusable.
> Additionally, your correspondent must initialize Blowfish with exactly
> the same initial values as you do.
> If you wish to try, I can E-Mail you files where some popular constants
> have been computed up to 16384 hex places. There are files for "e",
> ln(2),
> sin(1), sqrt(2) and several others. Have fun, initialize Blowfish in any
> of alternative ways...
Thanks, the idea was to just compute something for the sboxes at runtime
and avoid holding the 4kb of stuff. I will change it in CB, and if
anyone could look over cb [I have but I may have missed something] that
would be great.
Tom
--
CB: http://24.42.86.123/cb.html
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Mersenne RNG, RNG questions
Reply-To: [EMAIL PROTECTED]
Date: Mon, 10 Apr 2000 00:53:00 GMT
James Thye <[EMAIL PROTECTED]> wrote:
: Put quickly: Does anyone have any opinions of Mersenne Twister PRNG?
: I've been looking for a repeatable PRNG (same sequence of PRNGs can be
: generated given the same starting seeds). I've recently ran across the
: Mersenne Twister PRNG (no I'm not affliated with them in any way). It
: claim a period of 2^19937 - 1, which is incredible. [...]
I believe Sean Luke (see http://www.cs.umd.edu/users/seanl/gp/) recently
mentioned that use of the MT was contraindicated for stream cypher
applications. I /presume/ this means that it does not adequately
resist active attack.
: Second question: Can a questionable PRNG be improved by XORing its
: output with a cryptographic based PRNG, or would the new period be the
: Greatest Common Multiple of their respective periods?
The new period is not guaranteed to exceed the *least* common multiple
(http://hissa.nist.gov/dads/HTML/lestcmmnmltp.html).
This doesn't mean that XORing two near random streams together doesn't
normally produce an output which is closer to randomness than either
alone, though.
I wonder what can be done to encourage questions like this to appear in
sci.crypt.random-numbers... ;-)
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Be good, do good.
------------------------------
From: <[EMAIL PROTECTED]>
Subject: Re: Skipjack algorithm.
Date: 10 Apr 2000 01:17:26 GMT
Bill Unruh <[EMAIL PROTECTED]> wrote:
> This is on the basis of what theory? You admit in the rest of your post
> tht you do not have the competence to evaluate the security of a crypto
> system, and then come up with this comment?
That's a harsh statement, I can evaluate the security of a cryposystem, but I
don't know every cryptanalytic method,
do you? I'd be impressed, considering most haven't been invented yet. My base of
cryptographic knowledge tells me
skipjack with a longer key is more secure, I was looking for evidence to the contrary.
I haven't had years to study any
of the AES algorithms nor skipjack, but since the USG uses it to encrypt some military
type traffic, I'd like to have a
stronger version of it for consumer use if possible, not asking too much I hope.
------------------------------
Subject: Re: Blowfish constants
From: stanislav shalunov <[EMAIL PROTECTED]>
Date: Mon, 10 Apr 2000 01:55:58 GMT
Tom St Denis <[EMAIL PROTECTED]> writes:
> Do the constants in blowfish [for the sbox/pbox] have to be pi?
Blowfish constants were picked to be the digits of pi, because pi
looks random. If you compress pi with gzip it won't shrink.
If you use other constants, it's a different cipher. It may or may
not be secure, but it's a matter of separate study. It would be
extremely unwise and misleading to call this cipher "Blowfish."
If you're looking to save space, your design criterion is contrary to
the motivation for choice of original constants. It'll probably make
the cipher less secure.
On the other hand, if you change pi to e--or to a sequence of bits
produced by coin-flipping--the cipher would probably be as strong as
Blowfish. Still, don't call it Blowfish, because it's not.
--
stanislav shalunov | Speaking only for myself.
My address in From: is correct; if yours isn't, I don't want to hear from you.
Try to reply in newsgroup. I don't need courtesy copies.
------------------------------
** 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
******************************
