Cryptography-Digest Digest #237, Volume #13 Tue, 28 Nov 00 23:13:00 EST
Contents:
Re: Blum Blum Shub ([EMAIL PROTECTED])
Re: A Simple Voting Procedure (David Schwartz)
Re: Isomorphic Elliptic Curves (Roger Schlafly)
Re: Public key encryption in Javascript? ("William A. McKee")
Re: collision probability with file checksums (David Wagner)
Re: Public key encryption in Javascript? (John Bailey)
Re: collision probability with file checksums (Sundial Services)
Re: Public key encryption in Javascript? (Paul Rubin)
SRP - not good enough? (John Savard)
Re: projective coordinates in ECC: worth it? (Wei Dai)
Re: Entropy paradox (Scott Craver)
Re: How to find celebrity (Benjamin Goldberg)
Re: voting through pgp (Benjamin Goldberg)
New cipher idea (Benjamin Goldberg)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Blum Blum Shub
Date: Wed, 29 Nov 2000 00:56:58 GMT
Michal,
I believe that Baltimore Technologies offers Blum-Blum-Shub in there
crypto toolkit. I belive you can download a free copy.
-Jeff
In article <002b01c05970$a8424b20$70664cd5@ppp>,
[EMAIL PROTECTED] ("Michal Dobrowolski") wrote:
> This is a multi-part message in MIME format.
>
> --====NOFNSLNUZQNH0FNQH470
> Content-Type: multipart/alternative;
> boundary="----=_NextPart_000_0028_01C05979.06657080"
> Content-Disposition: inline
>
> ------=_NextPart_000_0028_01C05979.06657080
> Content-Type: text/plain;
> charset="iso-8859-2"
> Content-Transfer-Encoding: quoted-printable
>
> Hello everybody,
> Can anybody tell me where can I find implemented in C Blul Blum Shub =
> Random number generator, or just if U got it send it to me by mail.
I =
> need it of course just for my education.
> Greetings :)))
> Michal
>
> ------=_NextPart_000_0028_01C05979.06657080
> Content-Type: text/html;
> charset="iso-8859-2"
> Content-Transfer-Encoding: quoted-printable
>
> <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
> <HTML><HEAD>
> <META content=3D"text/html; charset=3Diso-8859-2" =
> http-equiv=3DContent-Type>
> <META content=3D"MSHTML 5.00.2614.3500" name=3DGENERATOR>
> <STYLE></STYLE>
> </HEAD>
> <BODY bgColor=3D#ffffff>
> <DIV><FONT face=3D"Arial CE" size=3D2>Hello everybody,</FONT></DIV>
> <DIV><FONT face=3D"Arial CE" size=3D2>Can anybody tell me where can I
=
> find=20
> implemented in C Blul Blum Shub Random number generator, or just if U
=
> got=20
> it send it to me by mail. I need it of course just for my=20
> education.</FONT></DIV>
> <DIV><FONT face=3D"Arial CE" size=3D2>Greetings :)))</FONT></DIV>
> <DIV><FONT face=3D"Arial CE"
size=3D2>Michal</FONT></DIV></BODY></HTML>
>
> ------=_NextPart_000_0028_01C05979.06657080--
>
> --====NOFNSLNUZQNH0FNQH470
> Content-Type: text/plain; charset=US-ASCII
> Content-Disposition: inline
> Content-Transfer-Encoding: 7bit
>
> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> Prezentacja oferty i sprzedaz produktow Twojej firmy w Centrum e-
biznesu
> teraz za niecala zlotowke dziennie!
> KLIKNIJ I ZAMOW http://www.getin.pl/centrum/es_logon.asp
>
> --====NOFNSLNUZQNH0FNQH470--
>
> --
> Posted from [194.153.216.125]
> via Mailgate.ORG Server - http://www.Mailgate.ORG
>
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: A Simple Voting Procedure
Date: Tue, 28 Nov 2000 17:03:09 -0800
"Kevin A. Roll" wrote:
> > 3) 3rd party can force voter to reveal the vote
[snip]
> How many times has 3) occurred in the history of the United States? Zero.
Huh? Have you forgotten the case where a Michigan judge ordered ten
voters to reveal their mayoral votes under penalty of perjury?
DS
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: Isomorphic Elliptic Curves
Date: Tue, 28 Nov 2000 18:28:43 -0800
David Wagner wrote:
> 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?
Oh yes, its real simple. For y^2 = x^3 + ax + b, it is something
like 4 + 27(b^3)/(a^2). Don't quote me, as I probably have a factor
wrong. The formula is very similar to that for the discriminant.
Formula might be different in characteristic 2. Also, the isomorphism
might be in the algebraic closure.
------------------------------
Reply-To: "William A. McKee" <[EMAIL PROTECTED]>
From: "William A. McKee" <[EMAIL PROTECTED]>
Subject: Re: Public key encryption in Javascript?
Date: Wed, 29 Nov 2000 02:40:35 GMT
I have a Java implementation of El Gamal. If your interested email me and
i'll send you a copy for free.
Cheers,
Will.
--
William A. McKee <[EMAIL PROTECTED]>
http://www.cjkware.com/wamckee/
Asia Communications Quebec Inc.
http://www.cjkware.com/
"We're starfleet: weirdness is part of the job." - Janeway
"I have seen things I cannot deny." - Scully
PGP public key at http://www.cjkware.com/wamckee/pgp/
Finger Print: F5B8 6251 050C 7595 6A84 6C37 6041 4258 1116 2FF2
"We need your help... " - http://www.distributed.net/
<[EMAIL PROTECTED]> wrote in message news:901fjf$lvm$[EMAIL PROTECTED]...
> 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] (David Wagner)
Subject: Re: collision probability with file checksums
Date: 29 Nov 2000 02:41:58 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Bryan Olson wrote:
>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.
I'm not sure I'm convinced yet.
I agree that collision-resistance is important if you want to have
the property of non-repudiation. However, non-repudiation is normally
associated with public-key schemes, and not with symmetric-key schemes.
I'd always thought of a manipulation detection code as a symmetric-key
scheme; is there any difference between a MDC and a MAC? If not,
it seems that non-repudiation is incompatable with the symmetric-key
property, because the key used for verification (which the receiver has)
can also be used to forge fake files.
In general, there are certainly secure MACs that are not collision-free.
An easy example is that any n-bit MAC allows the sender to find collisions
with just 2^{n/2} work. A more interesting example is the CBC-MAC,
which permits the construction of collisions with just O(1) work no
matter what the block size may be.
Should I find your reasoning compelling, given the above? Am I missing
something?
------------------------------
From: [EMAIL PROTECTED] (John Bailey)
Subject: Re: Public key encryption in Javascript?
Date: Wed, 29 Nov 2000 02:42:26 GMT
On Tue, 28 Nov 2000 23:37:20 GMT, [EMAIL PROTECTED] wrote:
>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...
Have a look at the source code behind:
http://www.frontiernet.net/~jmb184/interests/sci.crypt/small_num_expont.html
which impliments modular exponentiation in javascript
also
http://www.frontiernet.net/~jmb184/interests/sci.crypt/old_trunk/
which contain skeletal code for all public key functions (RSA like)
The problem with javascript is finding a way to use sufficiently long
numbers. I have considered trying to use a chinese remainder theorem
apporach to extend the number size of javascript but never got around
to it.
On a totally different tack, consider US Patent 4306111:
http://www.delphion.com/details?&pn=US04306111__ which is a simplified
knapsack
(quoting the patent summary)
public encryption key (c1, c2, r) in which r is the product of two
relatively prime numbers, and in which c1 and r, as well as c2 and r,
are relatively prime numbers, is used in an encryption algorithm x=c1
m1 +c2 m2 (mod r). The decryption algorithm will be equivalent to
solving simultaneous linear equations derived from the encryption
algorithm. Thus, both encrypting and decrypting are quite simplified
while still maintaining a high degree of security.
(end quote)
This one is probably flawed. A quick scan does not readily reveal why
its authors consider it immune from a straightforward application of
Euclid's algorithm.
I believe there is a distinct need for an encryption suite which
supports key exchange and for which the source code can be directly
inspected by the parties. There should be no more than slight
compromise on security level but it would be okay to restrict the
range of input to numbers only. Your post implied one other
compromise: encrypt only (eg use a larger system to decrypt) That
might be useful in some circumstances--eg key exchange with a
trustworth server.
John
John
------------------------------
Date: Tue, 28 Nov 2000 19:58:46 -0700
From: Sundial Services <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: collision probability with file checksums
I concur, David. I thought that the whole concept behind "message
digests" was that it would be impractical to "construct a <file> with
the <any particular> digest." Specifically to avoid the realistic
possibility of "substituting a malicious file without detection of the
substitution." ...
>David Wagner wrote:
>
> Bryan Olson wrote:
> >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.
>
> I'm not sure I'm convinced yet.
>
> I agree that collision-resistance is important if you want to have
> the property of non-repudiation. However, non-repudiation is normally
> associated with public-key schemes, and not with symmetric-key schemes.
>
> I'd always thought of a manipulation detection code as a symmetric-key
> scheme; is there any difference between a MDC and a MAC? If not,
> it seems that non-repudiation is incompatable with the symmetric-key
> property, because the key used for verification (which the receiver has)
> can also be used to forge fake files.
>
> In general, there are certainly secure MACs that are not collision-free.
> An easy example is that any n-bit MAC allows the sender to find collisions
> with just 2^{n/2} work. A more interesting example is the CBC-MAC,
> which permits the construction of collisions with just O(1) work no
> matter what the block size may be.
>
> Should I find your reasoning compelling, given the above? Am I missing
> something?
--
==================================================================
Sundial Services :: Scottsdale, AZ (USA) :: (480) 946-8259
mailto:[EMAIL PROTECTED] (PGP public key available.)
> Fast(!), automatic table-repair with two clicks of the mouse!
> ChimneySweep(R): "Click click, it's fixed!" {tm}
> http://www.sundialservices.com/products/chimneysweep
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: Public key encryption in Javascript?
Date: 28 Nov 2000 18:59:10 -0800
[EMAIL PROTECTED] (John Bailey) writes:
> I believe there is a distinct need for an encryption suite which
> supports key exchange and for which the source code can be directly
> inspected by the parties.
If the parties don't trust each other, it doesn't matter whether the
encryption is any good. The party at the other end of a connection
can misuse the information regardless of whether the connection is secure.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: SRP - not good enough?
Date: Wed, 29 Nov 2000 03:23:31 GMT
In SRP, the host computer stores the values s and v, where v is a
public key, derived from a private key calculated from a hash of s and
the user's password.
This means that a dictionary attack can be mounted on the password
file, since for each password tried, one just performs two direct
computations: hash s and P, then calculate a public key from a private
key.
One does *not* have to crack a public key problem for every password
tried.
The dictionary attack is somewhat more expensive, because a public-key
computation is slower than a conventional encryption or a hash
function, but not extraordinarily so.
(I was trying to take a look at PAK, to see if it is better, but I
can't seem to get through right now.)
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Wei Dai <[EMAIL PROTECTED]>
Subject: Re: projective coordinates in ECC: worth it?
Date: Tue, 28 Nov 2000 19:38:10 -0800
In article <[EMAIL PROTECTED]>, phr-n2000
@nightsong.com says...
> Doing ECC over GF(p): is there a significant practical speedup by
> representing all the points in projective coordinates, and normalizing
> at the end? That adds a bunch of scalar multiplication mod p at each
> step but puts off a GCD calculation til the very end. But it makes
> the formulas look even messier than before. Anyone have any practical
> advice, other than "implement it both ways and take benchmarks"?
> I'll be using a pretty slow bignum library, if that matters.
It depends on how slow modular inversion (extended GCD) is compared to
modular multiplication. The slower it is, the more attractive using
projective coordinates becomes. I think the break-even point is about a
factor of 5. That is, if a modular inversion takes more than about 5
times as long as a modular multiplication then projective coordinates
would be faster. This is true for state-of-the-art algorithms, but in
your case it's hard to say since I don't know what algorithms your
"slow" bignum library is using.
--
cryptopp.com - a free C++ class library of cryptographic schemes
------------------------------
From: [EMAIL PROTECTED] (Scott Craver)
Subject: Re: Entropy paradox
Date: 29 Nov 2000 03:30:43 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
>I am not arguing about 'theoretical' entropy or state etc.,
>but practically unpredictable (hence useful) bits.
Then there is, still, no paradox.
>M. K. Shen
-S
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: How to find celebrity
Date: Wed, 29 Nov 2000 03:52:21 GMT
James Felling wrote:
>
> [EMAIL PROTECTED] wrote:
>
> > Among n people, a celebrity is someone who everyone knows but who
> > knows no one. To identify the celebrity, if one exists, you are
> > allowed to ask questions of any of the n people, but only of the
> > form: "Excuse me, do you that person over there?" Assume that all
> > answers are correct. Minimize the number of questions you need to
> > ask to determine the celebrity, if one exists, or to determine no
> > celebrity exists in a given set of n people.
> >
> > suggestions please
>
> Learn basic induction.( this problem is easily solved through the use
> of mathematical induction)
>
> the answer as to the minimum is n^2-n. The question then is why is
> this true?
Actually, the answer is in O(N), not O(N**2) -- actually between 2N-2 in
the best case, and 3N-2 in the worst case.
Done properly, each of the first N-1 questions asked eliminated exactly
one person from the set of people who might possibly be a celebrity.
There is then exactly one person left, who might or might not be a
celebrity, and this needs close to 2(N-1) questions to determine if this
is so (slightly fewer, because some of the questions have already been
asked).
I have some psuedocode showing how to do this down below.
Other good questions are:
1) In what order would you ask the questions to get the minimum?
2) what is the minimum number of questions in the worst case? (3N-2)
3) what is the minimum number of questions in the best case? (2N-2)
4) what is the minimum number of questions in the average case?
(I dunno, I think this might be a difficult problem)
The method I believe would be optimal for identifying the celebrity is
this:
Set S = an ordered set of all the people (initially size N)
Set T = a copy of set S
While( |S| > 1 )
X = knows( S[0], S[1] ) ? 0 : 1;
// If S[0] knows anyone, S[0] is not a celebrity
// If S[1] is not known, S[1] is not a celebrity
S -= { S[X] };
}
// It is quite clear that the above takes exactly N-1 questions.
// If we know that there exists exactly one celebrity in the group
// we can stop here.
// Having eliminated all of the people who cannot be a celebrity, we
// are left with one person who might be a celebrity. However, since
// it is possible that the crowd contains no celebrities at all, this
// might be a false positive, so we need to confirm that the one person
// in set S actually is one.
foreach person P in ( T - { S[0] } )
if( knows( S[0], P ) )
There is no celebrity
if(!knows( P, S[0] ) )
There is no celebrity
// The above takes between N-1 and 2N-1 questions, depending on how
// many are repeat questions from the first loop.
S[0] is the celebrity
Note that S would be best implemented as a linked list, not an array.
The "knows" function keeps a cache of all answers, and doesn't count as
a question unless it hasn't been asked before. The cache is only needed
for the second loop, and if the cache is left out, the second loop takes
2N-2 questions to prove that S[0] is a celebrity.
--
There are three methods for writing code in which no bug can be found:
1) Make the code so straightforward that there are obviously no bugs.
2) Make the code so complicated that there are no obvious bugs.
3) Insist that any apparent bugs were really intentional features.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: voting through pgp
Date: Wed, 29 Nov 2000 03:52:28 GMT
David A Molnar wrote:
[snip]
> Again this is a user interface issue, and we don't seem to
> need electronic voting, strictly speaking. We can build
> mechanical mechanisms which enforce only voting for one
> candidate (radio buttons), do not register a vote until
> all offices have a vote, etc. There's probably lots of
> tricky issues involved, but I don't see that we need
> electronic voting. Maybe a system in which the ballot is
> marked by a mechanical mechanism and then available for
> inspection by the voter before finally being deposited
> would work -- but what happens when they silently
> malfunction and no one notices?
Actually, I believe that something like that exists in some places. I
live in New York state, and although I haven't participated in the
recent election, I think that voting machines which do this are used.
Moving the lever for one candidate would cause any other lever for a
candidate for that position to be reset. (Rather like a radio button)
A large lever at the bottom of the rows of voting levers simultaneously
did three things: It commited that person's vote, presumably by
punching a card, or incrementing a counter; it moved all of the vote
levers to their start position so noone could see who had been voted
for; and it opened the curtain at the front of the voting which
prevented people from looking over the person's shoulder. This also
helps prevent someone from voting more than once -- if the curtain
opened, you had voted -- there is no way to vote twice without the
curtain opening and closing in between.
About your idea of allowing the voter to "inspect the ballot" -- I don't
think that the machines even have actual punched or printed ballots --
just mechanical counters (kinda like odometer counters).
--
There are three methods for writing code in which no bug can be found:
1) Make the code so straightforward that there are obviously no bugs.
2) Make the code so complicated that there are no obvious bugs.
3) Insist that any apparent bugs were really intentional features.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: New cipher idea
Date: Wed, 29 Nov 2000 03:52:31 GMT
I'd like your comments on the following new cipher idea. It is similar
(in a minor way) to AES in that it's round is a linear step, followed by
a non-linear step, followed by a key mixing step.
Assume that sbox is bijective and highly non-linear, that the LFSR
polynomials are "dense." Considering all 8 polynomials at once, for
each power of x, at least one poly must has a coefficient of 1. Also,
assume that key approximates a random function of the user key.
The block size is 128 bits.
The global variable mask contains coefficients for 8 parallel (using
SIMD) order 16 primitive polynomials in GF(2)^N.
void encrypt( uint8 * txt, uint8 * key ) {
uint8 buf[32];
int i, j;
for( i = 0; i < 16; ++i )
buff[i] = txt[i] + *key++;
for( i = 0; i < rounds; ++i ) {
for( j = 0; j < 16; ++j ) {
int k, x;
for( x = buff[j], k = 1; k < 16; ++k )
x ^= buff[j+k] & mask[k];
buff[j|16] = x;
}
// buff[16..31] now contains the output of 8 order 16
// LFSRs. Thus, it is a linear transformation of the
// input.
for( j = 0; j < 16; ++j )
buff[j] = sbox[ buff[j|16] ] ^ *key++;
// Combining the nonlinear step and key addition step
// makes it a tad faster.
}
}
One possible of this cipher which I can see is that, if just a single
round is considered, cycling a single byte through all 256 values will
result in the output of the round cycling through all 256 values, with
100% probability. However, due how the linear step works, cycling one
byte through all possible values should result in other bytes in the
block changing in at least one bit each. The nonlinear step will cause
these bit changes to affect other bits in each byte. The linear step in
the *next* round will bring all of these changes back to that byte, in a
manner that that should be difficult for an attacker to predict. Thus,
no differential should hold with high probability for more than one
round.
I'll also admit that I don't understand linear cryptanalysis, but if the
sboxen are good, I think that this cipher will be strong against it.
Each of the layers can be independently paralleled in hardware -- it is
easy to calculate which bits of the input each output bit the linear
layer produces; each byte in the nonlinear layer is independent of it's
neighbors; the key addition step can also be done in parallel across the
block.
If sparse polynomials are used, instead of dense ones, the cipher might
be made faster, but more rounds will be needed for an equivilant level
of security.
Key expansion might be something similar to encryption, but would, for
192 and 256 bit keys, use order 24 and order 32 polynomials,
respectively. I haven't yet designed a key schedule for this cipher,
however, and suggestions would be appreciated.
--
There are three methods for writing code in which no bug can be found:
1) Make the code so straightforward that there are obviously no bugs.
2) Make the code so complicated that there are no obvious bugs.
3) Insist that any apparent bugs were really intentional features.
------------------------------
** 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
******************************
