Cryptography-Digest Digest #596, Volume #13 Wed, 31 Jan 01 05:13:00 EST
Contents:
Digits of PI (Benjamin Goldberg)
Re: fast signing (Thomas Wu)
Re: Ciphertext Stealing question (Benjamin Goldberg)
Re: More About Passwords (John Savard)
Re: Digits of PI (Paul Rubin)
Re: Shared key protocols (Ichinin)
Re: Digits of PI (Jim Gillogly)
Re: Digits of PI (Paul Rubin)
Re: Digits of PI (Benjamin Goldberg)
A new cipher ("David Finch")
Re: Digits of PI (Jim Gillogly)
Re: Digits of PI (Roger Schlafly)
Re: Digits of PI (Benjamin Goldberg)
Re: fast signing (Paul Crowley)
Re: On combining permutations and substitutions in encryption (Mok-Kong Shen)
----------------------------------------------------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Digits of PI
Date: Wed, 31 Jan 2001 07:03:04 GMT
I'm trying to calculate the base-256 digits of PI to use as "random"
constants in an algorithm. Unfortunatly, the formula I tried to use
[which is supposed to calculate the base-16 digits of pi] gives real,
rather than integral, values. The formula is:
____
\ ( 4 2 1 1 ) ( 1 )n
pi = \ ( ------ - ------ - ------ - ------ ) * ( -- )
/ ( 8n + 1 8n + 4 8n + 5 8n + 6 ) ( 16 )
/___
For the 0th..3rd hexadecimal digits of pi, this resulted in
3.13333333, 0.129426129/16, 0.0422205246/256, 0.0207553366/4096.
Clearly, I'm doing something wrong, or at least interpreting what the
formula is supposed to mean wrong.
I want to fill a 512 byte array with the first 1024 hexadecimal digits
of pi. Suggestions, please?
--
Most scientific innovations do not begin with "Eureka!" They begin with
"That's odd. I wonder why that happened?"
------------------------------
From: Thomas Wu <[EMAIL PROTECTED]>
Subject: Re: fast signing
Date: 30 Jan 2001 23:06:15 -0800
Bob Silverman <[EMAIL PROTECTED]> writes:
> In article <[EMAIL PROTECTED]>,
> Paul Rubin <[EMAIL PROTECTED]> wrote:
> > Bob Silverman <[EMAIL PROTECTED]> writes:
> > > I'm just making his suggestion public. I've let e be large.
> > > We get d = 3 and now signing is very fast and verification slow,
> > > instead of the other way around....
> >
> > Um, now that the signing exponent is known, the signatures don't
> > authenticate much any more...
>
> Sure. But how is it known? All you do is publish e. How
> does someone else know then that d = 3? phi(n) is still unknown,
> so there is no way to compute d from e....
Given n and e, can't you take some x, compute c=x^e (mod n), and
then go through a bunch of d's, checking if c^d==x (mod n)?
Under normal circumstances, d is huge, so brute-forcing it doesn't
make sense, but if d is fewer than, say, 40 bits...
> --
> Bob Silverman
> "You can lead a horse's ass to knowledge, but you can't make him think"
>
>
> Sent via Deja.com
> http://www.deja.com/
Tom
--
Tom Wu * finger -l [EMAIL PROTECTED] for PGP key *
E-mail: [EMAIL PROTECTED] "Those who would give up their freedoms in
Phone: (650) 723-1565 exchange for security deserve neither."
http://www-cs-students.stanford.edu/~tjw/ http://srp.stanford.edu/srp/
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Ciphertext Stealing question
Date: Wed, 31 Jan 2001 07:15:22 GMT
John Savard wrote:
>
> On Wed, 31 Jan 2001 04:02:09 GMT, Benjamin Goldberg
> <[EMAIL PROTECTED]> wrote, in part:
>
> >Otherwise, simply using the value 0 as
> >IV will work fine.
>
> Not if you're planning to use the same key for more than one message.
He's already said, and I quote, "the ciphertext must be the exact length
of the plaintext." This means that he can't have an IV sent with the
message. Period. He is [must be] willing to accept the fact that his
opponent will be able to identify when he sends messages with identical
content.
Being able to use side-channel information (like TCP/UDP port #, or
filesystem inode#, etc) as an IV is a bonus, and not something we can
count on. Lacking the bonus, we a limited to a constant IV.
--
Most scientific innovations do not begin with "Eureka!" They begin with
"That's odd. I wonder why that happened?"
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: More About Passwords
Date: Wed, 31 Jan 2001 07:10:10 GMT
On Wed, 31 Jan 2001 06:16:33 GMT, [EMAIL PROTECTED]
(John Savard) wrote, in part:
>It contains the two random
>values, the user's salt value, and the host computer's nonce public
>key. Note that the nonce public key must not be 'obvious' in a
>brute-force search: so we are using EKE at this step.
This is where the protocol fails. Since this contains the salt value,
and is encrypted only with the hash of the user's password, this can
be used in conjunction with the value on the host computer to do a
brute-force search for the user's password.
To repair the protocol, the following needs to be done:
When initially sending the user ID to the host computer, the user must
also enter the password at that time. Then, the user's computer
generates a random value, hashes it, encrypting the result by the
one-way hash of the user's password. Then, the random value, and the
final encrypted result, are together encrypted by the security
computer's public key.
The security computer will then only generate a result containing the
salt _if_ this value, passed on to it by the host computer, confirms
the user's identity - and the salt (if not the rest of that message)
will be encrypted with the random value from the user's computer, in
addition to the first-order hash of the password, to prevent
brute-force searches for the password.
*Now* we have a workable protocol.
1) User to user's computer: UID, UPASS
2) User's computer
- generates random value UR1
3) User's computer to host computer: UID + EPK(H(UR1) + E(H(H(UR1)),
H(UPASS) ), SPUB )
4) Host computer
- generates nonce public/private key pair HPUB, HPRV
- generates random value HR
5) Host computer to security computer: UID + EPK(H(UR1) + E(H(H(UR1)),
H(UPASS)), SPUB) + EPK(HR + HPUB, SPUB)
6) Security computer
- generates random value SR
- knows SPRV, and thus can decrypt the message
- knows H(UPASS), and thus can verify that E(H(H(UR1)), H(UPASS))
matches H(UR1) [halt if verify fails here]
- knows USALT
7) Security computer to host computer: Message M, which equals
E(E(USALT + HR + SR + HPUB, H(UPASS)), H(UR1))
8) Host computer
- retains a copy of message M
9) Host computer to user's computer: Message M, which equals E(E(USALT
+ HR + SR + HPUB, H(UPASS)), H(UR1))
10) User's computer
- knows H(UR1) and H(UPASS), and thus can obtain USALT, HR, SR,
and HPUB
- calculates UVERIFY, which is H(E(H(UPASS), USALT)); note that
USALT prevents guessing attacks on UVERIFY
11) User's computer to host computer: EPK(UR1 + H(E(E(E(M, H(UR1)),
HR), UVERIFY)), HPUB)
12) Host computer
- knows HPRV, UVERIFY, and HR, and can obtain UR1 and verify
H(E(E(E(M, H(UR1)), HR), UVERIFY))
- can hash UR1 and compare it to the original H(UR1) it was given
At this point, the user is authenticated, and a session key can be
used which combines UR1 and HR.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: Digits of PI
Date: 30 Jan 2001 23:54:57 -0800
If you're using Unix/Linux, try this:
% bc -l
scale = 500
obase = 16
4 * a(1)
That computes 4*arctan(1) (= pi) to 500 digits of precision ("scale")
and prints out the answer in base 16.
------------------------------
From: Ichinin <[EMAIL PROTECTED]>
Subject: Re: Shared key protocols
Date: Wed, 31 Jan 2001 07:54:23 GMT
You'd find the protocols section of Applied Cryptografy enlightening,
Also a number of key agreement/key negotiation protocols are available
in the conference papers. IIRC, Springer.de allow you to download a few
individual papers. www.securityfocus.com and www.counterpane.com also
have some links on the subject.
Minor note: Shared key communications may not be the same as key
agreement (like DH) IMHO; DH is more key negotiation since both systems
compute the sesson key.
Regards,
Ichinin
(Crypto novice)
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Digits of PI
Date: Wed, 31 Jan 2001 00:03:27 -0800
Benjamin Goldberg wrote:
> ____
> \ ( 4 2 1 1 ) ( 1 )n
> pi = \ ( ------ - ------ - ------ - ------ ) * ( -- )
> / ( 8n + 1 8n + 4 8n + 5 8n + 6 ) ( 16 )
> /___
...
> I want to fill a 512 byte array with the first 1024 hexadecimal digits
> of pi. Suggestions, please?
Here's a sci.crypt implementation of this formula from half a decade ago:
http://the.wiretapped.net/security/cryptography/libraries/math/gen-pi
Or, if you'd rather just look up the digits, do a search on Blowfish
and pluck the hex digits out of there; or look up John Savard's web
site and grab the ones he calculated for Quadiblock.
--
Jim Gillogly
Mersday, 10 Solmath S.R. 2001, 07:56
12.19.7.16.15, 1 Men 18 Muan, Second Lord of Night
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: Digits of PI
Date: 31 Jan 2001 00:07:17 -0800
Benjamin Goldberg <[EMAIL PROTECTED]> writes:
> For the 0th..3rd hexadecimal digits of pi, this resulted in
> 3.13333333, 0.129426129/16, 0.0422205246/256, 0.0207553366/4096.
> Clearly, I'm doing something wrong, or at least interpreting what the
> formula is supposed to mean wrong.
> I want to fill a 512 byte array with the first 1024 hexadecimal digits
> of pi. Suggestions, please?
I posted separately about computing the digits with "bc", but also,
I don't think you're supposed to expect integer results from the
Borwein formula you posted. See Borwein's paper about it. It is
very terse but absolutely wonderful.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Digits of PI
Date: Wed, 31 Jan 2001 08:23:02 GMT
Jim Gillogly wrote:
>
> Benjamin Goldberg wrote:
> > ____
> > \ ( 4 2 1 1 ) ( 1 )n
> > pi = \ ( ------ - ------ - ------ - ------ ) * ( -- )
> > / ( 8n + 1 8n + 4 8n + 5 8n + 6 ) ( 16 )
> > /___
> ...
> > I want to fill a 512 byte array with the first 1024 hexadecimal
> > digits of pi. Suggestions, please?
>
> Here's a sci.crypt implementation of this formula from half a decade
> ago:
>
> http://the.wiretapped.net/security/cryptography/libraries/math/gen-pi
That's perfect, thanks!
One silly little question, though... If I have 32 bit ints, and 16 bit
shorts, wouldn't it be faster to calculate using shorts rather than
chars?
--
Most scientific innovations do not begin with "Eureka!" They begin with
"That's odd. I wonder why that happened?"
------------------------------
From: "David Finch" <[EMAIL PROTECTED]>
Subject: A new cipher
Date: Wed, 31 Jan 2001 08:29:39 GMT
There seem to be a lot of bright people on this newsgroup. I recently wrote
a new encryption algorithm but I'm having trouble determining it's strength
with a fair level of certainty. It passes all of the typical tests. A single
bit change in either the key or the plaintext results in a completely
different ciphertext. The character frequencies are about what you would get
from random data. After I first wrote it, I spent several days looking for
and fixing all the theoretical weaknesses I could find. I designed it to be
simple to understand, fast on 32bit processors, and secure enough that you
would probably need brute force to break it.
There are no random lookup tables used in the encryption, which should make
it easier to spot any major weaknesses.
You can specify multiple rounds, but hopefully 1 round will be enough.
I need people who have free time and are willing to try to break it without
getting paid, since I'm in college and therefore have no money.
The source code and exe can be found at:
http://www.geocities.com/dtfinch/DC1.html
Any help would be much appreciated.
-David Finch <[EMAIL PROTECTED]> ICQ#9869494
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Digits of PI
Date: Wed, 31 Jan 2001 00:36:41 -0800
Benjamin Goldberg wrote:
> One silly little question, though... If I have 32 bit ints, and 16 bit
> shorts, wouldn't it be faster to calculate using shorts rather than
> chars?
You're doing it one time to initialize your variables, and Krueger's
program takes less than a second to generate your 1024 hex digits on
my laptop. How much faster do you need it to be?
--
Jim Gillogly
Mersday, 10 Solmath S.R. 2001, 08:35
12.19.7.16.16, 2 Cib 19 Muan, Third Lord of Night
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: Digits of PI
Date: Wed, 31 Jan 2001 00:59:10 -0800
Paul Rubin wrote:
> Benjamin Goldberg <[EMAIL PROTECTED]> writes:
> > For the 0th..3rd hexadecimal digits of pi, this resulted in
> > 3.13333333, 0.129426129/16, 0.0422205246/256, 0.0207553366/4096.
> > Clearly, I'm doing something wrong, or at least interpreting what the
> > formula is supposed to mean wrong.
> > I want to fill a 512 byte array with the first 1024 hexadecimal digits
> > of pi. Suggestions, please?
> I posted separately about computing the digits with "bc", but also,
> I don't think you're supposed to expect integer results from the
> Borwein formula you posted. See Borwein's paper about it. It is
> very terse but absolutely wonderful.
Not sure what you mean by this, but you could get bitten by a
rare rounding incident. Eg, if you get 3....5fffff... (in hex) then
you might have to calculate some more digits to see if the 5 should
really be a 6.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Digits of PI
Date: Wed, 31 Jan 2001 09:49:34 GMT
This is a multi-part message in MIME format.
==============B204B79246F5B1A98F97DF14
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
I'm trying to convert the algorithm you suggested from using 8 bit
values to using 16 bit values, and am having trouble. Could someone
point out what I am doing wrong? Part of the problem is that I don't
understand the algorithm, of course, but the change I'm making doesn't
*seem* like one which should break it. Maybe there's some overflow
occuring somewhere?
Both versions are attached.
--
Most scientific innovations do not begin with "Eureka!" They begin with
"That's odd. I wonder why that happened?"
==============B204B79246F5B1A98F97DF14
Content-Type: text/plain; charset=us-ascii; name="pi2.txt"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline; filename="pi2.txt"
/* Written by John J. Krueger, 2-14-1996 */
/* This code is free for anyone to use for anything they */
/* want on the condition that I will not be held liable for */
/* anything it does. */
/* This procedure will compute num_bytes bytes of Pi in */
/* binary (initial 3 not included) and store them in the */
/* user-allocated unsigned char array bytes. */
/* The last few digits may be wrong due to roundoff. */
/* This code is based on the following formula: */
/* infinity 4 2 1 1 */
/* ------ ----- ------- - ------- - ------- - ------- */
/* | | \ 8 i + 1 8 i + 4 8 i + 5 8 i + 6 */
/* | | = ) ------------------------------------- */
/* | | / i */
/* ----- 16 */
/* i = 0 */
/* This formula was found by Bailey, Borwein and Plouffe, */
/* more information can be found at: */
/* http://www.mathsoft.com/asolve/plouffe/plouffe.html */
#include <stdlib.h>
void compute_pi(int num_bytes, unsigned char *bytes)
{
div_t top;
int bot, i, j, k;
for(i=0;i<num_bytes;i++)
bytes[i]=0;
#define SUB_FROM_BYTES(a,b,c) \
top.rem=a;bot=b;\
for(i=c;i<num_bytes;i++)\
{\
top=div(top.rem<<8,bot);\
if((i>0)&&(top.quot>(int)bytes[i]))\
{\
j=i-1;\
bytes[j]--;\
while((j>0)&&(bytes[j--]==255))\
bytes[j]--;\
};\
bytes[i]-=top.quot;\
};
#define ADD_TO_BYTES(a,b,c) \
top.rem=a;bot=b;\
for(i=c;i<num_bytes;i++)\
{\
top=div(top.rem<<8,bot);\
if((i>0)&&(top.quot+(int)bytes[i]>255))\
{\
j=i-1;\
bytes[j]++;\
while((j>0)&&(bytes[j--]==0))\
bytes[j]++;\
};\
bytes[i]+=top.quot;\
};
#define DOIT(n,m,off) \
ADD_TO_BYTES( 4,(8*(n)+1)<<m,off);\
SUB_FROM_BYTES(2,(8*(n)+4)<<m,off);\
SUB_FROM_BYTES(1,(8*(n)+5)<<m,off);\
SUB_FROM_BYTES(1,(8*(n)+6)<<m,off);\
for(k=0;k<num_bytes;k++)
{
DOIT(2*k+0,0,k);
DOIT(2*k+1,4,k);
};
}
#include <stdio.h>
void pitest() {
unsigned char bytes[256];
int i;
compute_pi(256, bytes);
for( i = 0; i < 256; ++i )
printf("%02x",bytes[i]);
printf("\n");
}
==============B204B79246F5B1A98F97DF14
Content-Type: text/plain; charset=us-ascii; name="pi3.txt"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline; filename="pi3.txt"
/* Written by John J. Krueger, 2-14-1996 */
/* This code is free for anyone to use for anything they */
/* want on the condition that I will not be held liable for */
/* anything it does. */
/* This procedure will compute num_words words of Pi in */
/* binary (initial 3 not included) and store them in the */
/* user-allocated unsigned short array words. */
/* The last few digits may be wrong due to roundoff. */
/* This code is based on the following formula: */
/* infinity 4 2 1 1 */
/* ------ ----- ------- - ------- - ------- - ------- */
/* | | \ 8 i + 1 8 i + 4 8 i + 5 8 i + 6 */
/* | | = ) ------------------------------------- */
/* | | / i */
/* ----- 16 */
/* i = 0 */
/* This formula was found by Bailey, Borwein and Plouffe, */
/* more information can be found at: */
/* http://www.mathsoft.com/asolve/plouffe/plouffe.html */
#include <stdlib.h>
void compute_pi(int num_words, unsigned short *words)
{
div_t top;
int bot, i, j, k;
for(i=0;i<num_words;i++)
words[i]=0;
#define SUB_FROM_WORDS(a,b,c) \
top.rem=a;bot=b;\
for(i=c;i<num_words;i++)\
{\
top=div(top.rem<<16,bot);\
if((i>0)&&(top.quot>(int)words[i]))\
{\
j=i-1;\
words[j]--;\
while((j>0)&&(words[j--]==65535))\
words[j]--;\
};\
words[i]-=top.quot;\
};
#define ADD_TO_WORDS(a,b,c) \
top.rem=a;bot=b;\
for(i=c;i<num_words;i++)\
{\
top=div(top.rem<<16,bot);\
if((i>0)&&(top.quot+(int)words[i]>65535))\
{\
j=i-1;\
words[j]++;\
while((j>0)&&(words[j--]==0))\
words[j]++;\
};\
words[i]+=top.quot;\
};
#define DOIT(n,m,off) \
ADD_TO_WORDS( 4,(8*(n)+1)<<m,off);\
SUB_FROM_WORDS(2,(8*(n)+4)<<m,off);\
SUB_FROM_WORDS(1,(8*(n)+5)<<m,off);\
SUB_FROM_WORDS(1,(8*(n)+6)<<m,off);\
for(k=0;k<num_words;k++)
{
DOIT(4*k+0, 0,k);
DOIT(4*k+1, 4,k);
DOIT(4*k+2, 8,k);
DOIT(4*k+3,12,k);
};
}
#include <stdio.h>
void pitest() {
unsigned short words[128];
int i;
compute_pi(128, words);
for( i = 0; i < 128; ++i )
printf("%04x",words[i]);
printf("\n");
}
==============B204B79246F5B1A98F97DF14==
------------------------------
Subject: Re: fast signing
From: Paul Crowley <[EMAIL PROTECTED]>
Date: Wed, 31 Jan 2001 09:52:13 GMT
Bob Silverman <[EMAIL PROTECTED]> writes:
> In article <[EMAIL PROTECTED]>,
> Paul Rubin <[EMAIL PROTECTED]> wrote:
> > Bob Silverman <[EMAIL PROTECTED]> writes:
> > > I'm just making his suggestion public. I've let e be large.
> > > We get d = 3 and now signing is very fast and verification slow,
> > > instead of the other way around....
> >
> > Um, now that the signing exponent is known, the signatures don't
> > authenticate much any more...
>
> Sure. But how is it known? All you do is publish e. How
> does someone else know then that d = 3? phi(n) is still unknown,
> so there is no way to compute d from e....
NB for those new to crypto: those ellipses on the end of Bob's
sentences mean he's being funny. Don't do as he suggests.
Hmm, I wonder if anyone has done as he satirically proposes in any
fielded systems? Next time someone's attacking amateurish RSA crypto
with a large, random-looking e, it might be worth a go...
--
__
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On combining permutations and substitutions in encryption
Date: Wed, 31 Jan 2001 11:07:08 +0100
Terry Ritter wrote:
>
[snip]
> It should be obvious that XOR does not protect the confusion stream
> against exposure from known-plaintext. A keyed Latin square provides
> some protection, so it is also obvious that various amounts of such
> protection are possible. What we do not know -- because it is not
> addressed in the cryptographic literature -- is how far that process
> can go.
I am afraid that you have yourself pointed to the practical
unsolvablility of the problem. How could one quantify the
'some' in 'some protection', and that objectively?
Such matters have hitherto not been addressed in the
literature, because the authors naturally (and can) only
publish (perhaps only choose to do) those stuffs that can
be nicely (maybe also easily) done with strict mathematical
means, I suppose. BTW, in this point, associations with
'fuzzy logic' and 'naive physics' come to mind. But I don't
believe analogous stuffs would ever be accepted by the
crypto community.
M. K. Shen
=============================
http://home.t-online.de/home/mok-kong.shen
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
