Cryptography-Digest Digest #236, Volume #13 Tue, 28 Nov 00 20:13:01 EST
Contents:
Safe Primes p=g+x^2 ([EMAIL PROTECTED])
Re: Q: Role of linguistics (Mok-Kong Shen)
Re: Q: Role of linguistics (John Savard)
Wanted: RC5 testvectors. ([EMAIL PROTECTED])
Re: Entropy paradox (Mok-Kong Shen)
Rijndael applications ("Red Shadow")
Re: Q: Role of linguistics (Mok-Kong Shen)
Re: Q: Role of linguistics (Tom St Denis)
Re: Wanted: RC5 testvectors. (Tom St Denis)
Re: DES question: Has this ever been proven before? (David Wagner)
Re: Isomorphic Elliptic Curves (David Wagner)
Re: P/w based authentication and key exchange (Thomas Wu)
Public key encryption in Javascript? ([EMAIL PROTECTED])
Re: RSA: Choice of p,q dependent on input size? (Bill Unruh)
Re: Entropy paradox (John Savard)
Re: Entropy paradox (John Savard)
Re: collision probability with file checksums (Bryan Olson)
Re: A Simple Voting Procedure (Kevin A. Roll)
Re: A Simple Voting Procedure (Kevin A. Roll)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Safe Primes p=g+x^2
Date: Tue, 28 Nov 2000 22:12:52 GMT
I need to create a set of 1024bit safe prime numbers
which share a primitive root for use in my SNAKE
key exchange algorithm ( http://www.kripto.org/snake )
To do this, Im finding safe primes of the form...
p=g+x*x
where g is an arbitrary number Ive chosen to be the
primitive root, and x is >=4.
I chose g to be the first (lowest) safe 1024bit prime,
and so far Ive generated some 2400 safe primes for
which this is a primitive root.
Ive made some interesting observations which I was
hoping someone (better at number theory than I am)
could explain...
1) p mod 16 is either 3, 9, or 15.
2) All values for x are multiples of 6.
3) If we store p in as bytes and sum all but
the first (0x80) byte, the resulting number
is always a multiple of 3.
Ive had a quick try generating 256bit, 128bit and 64bit
safe primes and they look to have the same results.
ttfn
PG.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Role of linguistics
Date: Tue, 28 Nov 2000 23:31:39 +0100
Tom St Denis wrote:
>
> I do not get what you are trying to say. Are you saying multilingual
> cryptographers are more capable?
No. But the attacks on historical schemes were apparently
facilitated with good knowldege of languages. I surmise
that the advances made possible by computers to linguistics
could provide some processing (encoding) steps that are
useful as components of modern encryption schemes.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Q: Role of linguistics
Date: Tue, 28 Nov 2000 22:27:19 GMT
On Mon, 27 Nov 2000 19:01:43 +0100, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote, in part:
>If I don't err, in the old days knowldege of languages played
>a non-trivial role in cryptanalysis. With modern cryptography,
>which works at the fine level of bits, the significance of
>linguistics to crypto seems to have disappeared completely.
>Could someone confirm this?
I would think this is the case. The reason is basically because
today's ciphers are quite strong, and operate on large blocks. Hence,
linguistic characteristics are well-obscured; cryptanalysts struggle
to find even known-plaintext and chosen-plaintext attacks.
>If the domain of discourse is appropriately
>restricted, wouldn't the limited number of sentence structures
>together with default words and eventually in combination with
>a code book be exploitable as a valuable means of preprocessing
>(encoding) of the plaintext before its treatment by a proper
>modern encryption algorithm?
The idea of using knowledge about language to improve text compression
is an interesting idea. But I don't think there is interest in it as
yet.
Although I remember, several years ago, a news item about some IBM
research in that area, an electronic version of the cable code books
of old.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED]
Subject: Wanted: RC5 testvectors.
Date: Tue, 28 Nov 2000 22:26:58 GMT
Hello,
I'm looking for some test vectors for RC5 in different round and key
settings. I'm only looking for single block test vectors (so I haven't
got much use for the test vectors in the RFC).
If you happen have test vectors for the expanded key that would be
useful too.
/ foo
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Entropy paradox
Date: Tue, 28 Nov 2000 23:40:14 +0100
Tom St Denis wrote:
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> >
> > James Felling wrote:
> > >
> > [snip]
> > > You assume that there is an overage and then use that assumption to
> > > prove that entropy is added. Why is it that you claim this overage
> of
> > > randomness must exist?
> >
> > If n of BBS is sufficiently large and the construction is
> > sound, one can generate a fairly large amount of output bits
> > that are practically unpredictable. That is, one inputs
> > into BBS a rather small amount of - also practically --
> > unpredictable bits and obtain as output a very large
> > amount of practically unpredictable bits. There could
> > perhaps be certain difference in 'quality' between these
> > two groups of bits, but as far as the user is concerned,
> > they are not. So, as long as the BBS cannot be brute-forced,
> > one has a huge gain in practically unpredictable bits. My
> > view is that this gain seems to come from 'nothing' (the
> > air), sort of via magic. That's what troubles me.
>
> The bits from the BBS generator are not "new" bits though. They are
> not random, merely unpredictable to a third party. New bits would be
> like injecting entropy into the state (i.e new modulus or a bigger one)
>
> You have to realize the difference between output and state. The
> entropy in the state (the system) does not change regardless of the
> length of the output. So the output does not increase the entropy.
> (hint: consider the output of a LFSR, does the output make the internal
> state any more random?)
I am not arguing about 'theoretical' entropy or state etc.,
but practically unpredictable (hence useful) bits.
M. K. Shen
------------------------------
From: "Red Shadow" <[EMAIL PROTECTED]>
Subject: Rijndael applications
Date: Tue, 28 Nov 2000 22:50:32 GMT
I'm a student of the university in Ghent and I'm writing a presenation on
Rijndael. I'm looking for some application or some systeem who are already
using this algoritme.
Thanx
Lieven
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Role of linguistics
Date: Tue, 28 Nov 2000 23:57:57 +0100
John Savard wrote:
>
> Mok-Kong Shen<[EMAIL PROTECTED]> wrote:
>
[snip]
> >If the domain of discourse is appropriately
> >restricted, wouldn't the limited number of sentence structures
> >together with default words and eventually in combination with
> >a code book be exploitable as a valuable means of preprocessing
> >(encoding) of the plaintext before its treatment by a proper
> >modern encryption algorithm?
>
> The idea of using knowledge about language to improve text compression
> is an interesting idea. But I don't think there is interest in it as
> yet.
>
> Although I remember, several years ago, a news item about some IBM
> research in that area, an electronic version of the cable code books
> of old.
I think that the sentence structures could be assigned
numbers with default words assigned to the nodes, i.e.
the number represents already a valid sentence. Some or
all of the words at the nodes are to be replaced by
others for the actual sentence (these words have code
numbers), thus resulting in an encoding. This is rather
primitive conceptually. I surmise that something more
sophisticated probably could be done.
M. K. Shen
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Q: Role of linguistics
Date: Tue, 28 Nov 2000 22:57:32 GMT
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
>
> Tom St Denis wrote:
> >
>
> > I do not get what you are trying to say. Are you saying
multilingual
> > cryptographers are more capable?
>
> No. But the attacks on historical schemes were apparently
> facilitated with good knowldege of languages. I surmise
> that the advances made possible by computers to linguistics
> could provide some processing (encoding) steps that are
> useful as components of modern encryption schemes.
Modern encryption schemes have nothing todo with human linguistics.
Perhaps breaking them in very specific circumstances could be
facilated... but it is not a key focus.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Wanted: RC5 testvectors.
Date: Tue, 28 Nov 2000 22:58:37 GMT
In article <901bfa$ibu$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Hello,
>
> I'm looking for some test vectors for RC5 in different round and key
> settings. I'm only looking for single block test vectors (so I haven't
> got much use for the test vectors in the RFC).
>
> If you happen have test vectors for the expanded key that would be
> useful too.
Why not see if your code is compatible with the RFC? just add the
required functions and see if they match.
Plus RC5 is really hard to get wrong, perhaps only the keyschedule is
troublesome.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: DES question: Has this ever been proven before?
Date: 28 Nov 2000 23:33:32 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Francois Grieu wrote:
>Yes, Knuth's TAOCP present this algorithm. But there is no reason that
>an ENTRY in the cycle, which is what we are looking after, is for some
>n with a(n) = a(2n) so IMHO the technique does not apply.
I think it does apply. Once you find n so that a(n) = a(2n), you know
the period of the cycle, and you can deduce the length of the "leader"
which enters the cycle, hence you can walk forward again from the starting
point to find the collision. All this can be done in linear time.
>Beside, it
>increases the number of iterations by a factor like 2, which is a serious
>issue in practice.
Yes, this is a more serious issue, and the method of distinguished points
is a useful way to avoid this problem.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Isomorphic Elliptic Curves
Date: 28 Nov 2000 23:34:15 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Bob Silverman wrote:
>Two curves are isomorphic iff they have the same j-invariant.
Out of curiousity, can the j-invariant be computed in polynomial time?
------------------------------
From: Thomas Wu <[EMAIL PROTECTED]>
Subject: Re: P/w based authentication and key exchange
Date: 28 Nov 2000 15:35:59 -0800
"Michael Scott" <[EMAIL PROTECTED]> writes:
> Its fun to try and develop such methods. What about this? Choose g and r as
> "random" independent generators of prime order q|(p-1). Let s be the low
> entropy mutual secret.
>
> Alice A=g^a . r^s mod p
> Bob B=g^b . r^s mod p
The discrete log of r (with base g and mod p) must remain unknown for this
to work, i.e. if an attacker found y such that g^y == r (mod p), he could
carry out an attack.
In any case, this is slower than PAK, which uses s directly instead of
r^s, and doesn't have any security advantage that I can see. The only
possible advantage is that you're operating in the q-order subgroup
mod p.
> Swap A and B
>
> Alice calculates key as (B/r^s)^a mod p = g^(xy) mod p
> Bob calculates key as (A/r^s)^b mod p = g^(xy) mod p
>
> Throw in a few hash functions and the odd random oracle, and does this work?
> Note that if s=0, then this is just Diffie-Hellman.
>
>
> Mike Scott
--
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: [EMAIL PROTECTED]
Subject: Public key encryption in Javascript?
Date: Tue, 28 Nov 2000 23:37:20 GMT
Hi. I'm looking for a public key (asymetric) encryption algorythm which
is simple enough to implement in javascript. No need for key
generation. I don't even think we need decryption in javascript.
I've looked around at various crypto libraries and they make my head
swim. Then I think about implementing them in braindead-slow
javascript...
All my work is opensource/GPL.
Can anyone point me in a helpful direction?
John
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: RSA: Choice of p,q dependent on input size?
Date: 29 Nov 2000 00:06:05 GMT
In <[EMAIL PROTECTED]> Kat Hopwood <[EMAIL PROTECTED]> writes:
>-----BEGIN PGP SIGNED MESSAGE-----
>Arild Kvalbein wrote:
>> My textbook in data security and cryptography includes the following
>> question as an exercise:
>>
>> "Find primes p and q so that 12-bit plaintext blocks could be encrypted
>> with RSA"
>The question is badly posed. If it is asking for a toy example of RSA
>primes without regard to security, then it's sufficient that pq > 2^12.
actually, 3 and 5 will do-- you can always break up that 12 bit block
into four 3 bit blcks and use RSA with N=15.
>If it is asking what size p and q should be in practice to encrypt a
>12-bit plaintext, they should each be at least 512 bits, and this does
>not depend on the size of the plaintext.
Well, then you better pad the text to make sure that it is larger than
sqrt(N), or it is trivial to break.
>(There is a maximum size that can be encrypted directly using RSA with
>an encoding method such as PKCS #1 v1.5 or OAEP, but for longer messages
>than that, a hybrid cryptosystem would normally be used, in which case
>the plaintext size still doesn't affect the size of the modulus.)
No, you just break it up into blocks all of which are smaller than
ln_2(N).
But I definitely agree that the problem is ill posed!
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Entropy paradox
Date: Wed, 29 Nov 2000 00:00:26 GMT
On Sat, 25 Nov 2000 10:12:29 +0100, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote, in part:
>Why shouldn't we put our feet
>on the floor of the read world and operate with real
>concepts?
I am operating with real concepts.
Brute-force search is a very real possibility.
And brute-force search is precisely what makes the big difference
between bits computed by an elaborate and secure means from an input
key and bits chosen by the use of a physical randomizer.
Entropy = size of brute-force search resisted : not increased even by
Blum-Blum-Shub.
G = quantity of plaintext that can be securely enciphered : increased
by Blum-Blum-Shub, and other cipher systems, quite easily, _provided
the entropy of the key was adequate in the first place_.
We shouldn't throw away a distinction which is very useful in
clarifying our thinking, and that has very important consequences in
the real world.
One reason that BBS output can possibly be 'just as good' as true
random bits is because the input key was beyond the horizon - over the
limit - of possible brute-force searches.
Only when one is dealing with smaller numbers of bits does entropy
become important. Start with a 20 bit key. No matter how 'provably
secure' your algorithm is, the sequence of bits it produces can always
be found in just over a million tries...so no algorithm can create
more entropy.
Start with a 2000 bit key, though, and since no one can ever find that
key through brute-force searching, whether or not you can generate
more than 2000 bits of keystream from it safely depends on the
security of your generator.
The provable security of BBS shows that it will work with a 2000 bit
key, but _not_ that it can do the impossible with a 20 bit key.
And we would have no way of knowing that if we didn't have a distinct
concept of entropy.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Entropy paradox
Date: Wed, 29 Nov 2000 00:08:51 GMT
On Sat, 25 Nov 2000 10:12:34 +0100, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote, in part:
>For me G is simply an approximate yet good estimate of
>'entropy' for which one unfortunately has no exact direct
>means of measurement.
Then you are mistaken. G is no such thing.
Sequences having large G but wildly different values of entropy cannot
be distinguished _when the entropy is over a sufficiently high
threshold_.
But when the entropy is below a critical limit, then no sequence can
have a G higher than its underlying entropy. That limit is the
threshold where brute-force search becomes possible.
When entropy is low, G is a measure of entropy.
When entropy is large, G is a measure of the length of the sequence,
and the security of the algorithm used to produce the sequence from
the starting entropy.
You could think of G as an approximation to entropy, but it doesn't
have a simple uniform behavior. It isn't always entropy to entropy
plus 50%. Essentially, when entropy is large enough to prevent
brute-force search, the numerical relationship of G to entropy *breaks
down*.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: collision probability with file checksums
Date: Wed, 29 Nov 2000 00:51:15 GMT
Ed L Cashin <[EMAIL PROTECTED]> wrote:
[...]
> If by "blind collision searches" you mean a birthday attack, then I
> understand why you say it takes 2^(n/2) tests, since it's easier when
> you can choose both the input and the output of the hash function.
>
> But we've been talking about a manipulation detection code on file
> contents.
No, the subject was collision search when the specific work
factors came up. The Van Oorschot and Wiener estimate is for
finding one collision, not a second pre-image.
> In that case, the attacker must try to match a hash output
> that is already there, which is harder, requiring 2^n tests. So David
> would be right.
Wagner and Schwartz are both "David". I side with Wagner.
Incidentally, a good manipulation detection code must be
collision resistant. Otherwise an attacker might be able to
construct an innocuous file and a malicious file with the same
digest, legally introduce the innocuous file, and then
substitute the malicious file without detection of the
substitution.
--Bryan
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Kevin A. Roll <[EMAIL PROTECTED]>
Subject: Re: A Simple Voting Procedure
Date: Tue, 28 Nov 2000 20:00:07 -0500
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
says...
> It seems there are some terminology confusion here. There are several
> distinct points:
> 1) the voter can tell if his vote is correctly counted
> 2) the voter can prove if his vote is incorrectly counted
> 3) 3rd party can force voter to reveal the vote
>
> Note that 2) is pretty much the same as 3) in that there are lots of
> scenarios involving corrupt official, revolutions, vote-buying, etc.
> that turns 2) into 3). So if you claim 1) and 2), you are logically
> claiming 3), which is objectionable to many people.
How many times has 3) occurred in the history of the United States? Zero.
How many times have 1) and 2) occurred? Difficult to say exactly, but
there have certainly been numerous cases of vote fraud. Prevent the vote
fraud and you should never have to worry about 3).
------------------------------
From: Kevin A. Roll <[EMAIL PROTECTED]>
Subject: Re: A Simple Voting Procedure
Date: Tue, 28 Nov 2000 20:03:16 -0500
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
says...
> Consider a system where each voter has an ID but no voter can prove
> which ID is his and no official can map an ID to a particular voter.
> When you vote, you are given a receipt (which is also ultimately made
> public) that proves that your ID voted for whichever candidate you
> actually voted for.
>
> When the election is complete, the list of voter IDs that voted for
> each candidate is presented.
>
> You have '1' because if you can check if your ID is on the correct list
> and you know your ID.
>
> You have '2' because you have a receipt that says that your ID voted
> for your candidate. If it appears on the wrong list, presenting your
> receipt demonstrates this error.
>
> You don't have '3' because no third party could ever be sure you were
> presenting your own receipt, as opposed to one some other voted made
> public. If all receipts are made public after the election, you can
> present anyone's receipt you choose -- that of literally any voter.
This is essentially the scheme that I started this thread with. After the
election is over, just throw away the receipt and your anonymity is
assured.
------------------------------
** 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
******************************
