Cryptography-Digest Digest #393, Volume #13 Wed, 27 Dec 00 12:13:00 EST
Contents:
Re: polynomial permutation cipher (Mok-Kong Shen)
Re: polynomial permutation cipher (Benjamin Goldberg)
Inventor of the digital signature concept ([EMAIL PROTECTED])
Re: RSA == hash function? ("Tom ST Denis")
Re: Cryptoanalysis Illegal ??? ("Jakob Jonsson")
Distributing private keys on the internet (Bob)
Re: ___(WANTED) UPDATED performance figures of elliptic curve multiplications
(Robert Harley)
Re: Distributing private keys on the internet (Benjamin Goldberg)
Re: Steganography using text as carrier ([EMAIL PROTECTED])
Re: Distributing private keys on the internet (Steve K)
ECDSA: adding the Point P with -P and restrictions of a & b ("Jesper Stocholm")
Re: Distributing private keys on the internet (Bob)
Block or stream cipher ("Wei Kok Ng")
Re: ECDSA: adding the Point P with -P and restrictions of a & b (Bob Silverman)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: polynomial permutation cipher
Date: Wed, 27 Dec 2000 10:27:28 +0100
Benjamin Goldberg wrote:
>
[snip]
> Here's a simple example:
> pt = a 128 bit value, or a poly of order at most 127
> ct[0..3] = each is a 32 bit value, or a poly of order at most 31
> py[0..3] = each is a different irreducible order-32 poly
> % = GF(2)[x] polynomial remainder (aka crc)
> * = GF(2)[x] polynomial multiplication
> + = GF(2)[x] polynomial addition (aka XOR)
>
> To encrypt, we take the crcs:
> for i in 0..3
> ct[i] = ( pt + x^128 ) % py[i];
>
> To decrypt, we use the CRT algorithm:
> pt = ct[0] * py[1] * py[2] * py[3] +
> ct[1] * py[0] * py[2] * py[3] +
> ct[2] * py[0] * py[1] * py[3] +
> ct[3] * py[0] * py[1] * py[2] +
> py[0] * py[1] * py[2] * py[3] + x^128;
>
> See? Lots of multiplications, but no inversions.
I am certainly confused. But from the last equation,
one obtains
( pt + x^128) % py[0] =
ct[0] * py[1] * py[2] * py[3] % py[0]
How could one show that this is identical to ct[0]?
Thanks.
M. K. Shen
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: polynomial permutation cipher
Date: Wed, 27 Dec 2000 10:09:48 GMT
Mok-Kong Shen wrote:
>
> Benjamin Goldberg wrote:
> >
> [snip]
> > Here's a simple example:
> > pt = a 128 bit value, or a poly of order at most 127
> > ct[0..3] = each is a 32 bit value, or a poly of order at most 31
> > py[0..3] = each is a different irreducible order-32 poly
> > % = GF(2)[x] polynomial remainder (aka crc)
> > * = GF(2)[x] polynomial multiplication
> > + = GF(2)[x] polynomial addition (aka XOR)
> >
> > To encrypt, we take the crcs:
> > for i in 0..3
> > ct[i] = ( pt + x^128 ) % py[i];
> >
> > To decrypt, we use the CRT algorithm:
> > pt = ct[0] * py[1] * py[2] * py[3] +
> > ct[1] * py[0] * py[2] * py[3] +
> > ct[2] * py[0] * py[1] * py[3] +
> > ct[3] * py[0] * py[1] * py[2] +
> > py[0] * py[1] * py[2] * py[3] + x^128;
> >
> > See? Lots of multiplications, but no inversions.
>
> I am certainly confused. But from the last equation,
> one obtains
>
> ( pt + x^128) % py[0] =
>
> ct[0] * py[1] * py[2] * py[3] % py[0]
>
> How could one show that this is identical to ct[0]?
Let t[0..3] be temp variables, and ignore for the moment the x^128 term.
t[0] = ct[0] * py[1] * py[2] * py[3]
Consider t[0] % py[1,2,3]. Since t[0] is a product of each poly, the
remainder modulo any of them is 0. Now consider t[0] % py[0]. Since
t[0] is a multiple of ct[0], t[0] % py[0] == ct[0] % py[0].
These relationships hold true for all t[i].
As for showing how the x^128 term is involved...
Let's consider two more temp values, ta and tb.
ta = sum(i=0..3) t[i]
tb = py[0] * py[1] * py[2] * py[3]
If x^128 is NOT added to pt before hand, then
ta = pt % tb
but since pt < tb
pt = ta
Read the Chinese Remainder Theorem to see why the above is true.
If x^128 is added to pt beforehand, this becomes:
ta = (pt + x^128) % tb
so pt = ta - x^128 % tb
But since -x^128 only makes it order-128, not higher, %tb becomes -tb.
so pt = ta - x^128 - tb
Thus you can see that adding it has a trivial effect on encryption.
Why bother adding it, then? Because if I didn't, then if the first
(128-32) bits of pt are 0, then all values of ct would = the lowest 32
bits of pt, and thus those bits would be leaked.
--
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: [EMAIL PROTECTED]
Subject: Inventor of the digital signature concept
Date: Wed, 27 Dec 2000 11:32:36 GMT
I wish to confirm that Diffie and Hellman* invented the idea of digital
signature or public key digital signature?
Is the concept of arbitrated symmetric key digital signature comes
after Diffie and Hellman's digital signature concept?
*W. Diffie and M. E. Hellman. New directions in cryptography. IEEE
Transactions on Information Theory, 22(5):644--654, November 1976.
Thank you.
W.S.Chong
[EMAIL PROTECTED]
Sent via Deja.com
http://www.deja.com/
------------------------------
From: "Tom ST Denis" <[EMAIL PROTECTED]>
Subject: Re: RSA == hash function?
Date: Wed, 27 Dec 2000 12:58:05 GMT
"Simon Johnson" <[EMAIL PROTECTED]> wrote in message
news:92bftj$a0o$[EMAIL PROTECTED]...
> Lets say:
> y=X^2 mod n
>
> This is the bit of answer i disagree with, you can't find x from y
> unless you factor N. So the preimage is secure if n is of the right
> size, regardless.
However, there are four collisions (four diff X will go to y when squared).
That's my point. With RSA it's worse.
> You attack could work theortically (your more likely to find a
> collision by brute-force) but with a hash size of say 4098-bits, it
> unlikely.
I agree.
Tom
------------------------------
From: "Jakob Jonsson" <[EMAIL PROTECTED]>
Subject: Re: Cryptoanalysis Illegal ???
Date: Wed, 27 Dec 2000 14:58:32 +0100
See http://www.parodie.com/english/smartcard.htm for a related real-life
story.
Jakob
"Mark Harrop" <[EMAIL PROTECTED]> skrev i meddelandet
news:[EMAIL PROTECTED]...
> Hi all...
>
> As you probably know from my earlier postings (asking where archives are)
> that I am a newbie, so pls pardon this question if it has been answered
> before, or is just plain stupid !
>
> From reading various books and postings on the Net, it is quite obvious
> how far the USA government will go to stop export etc. of Crypto devices
> and programs, but what is not quite obvious, or at least not to me ;-), is
> why they haven't tried to ban Cryptoanalysis ??
>
> Just in case I have missed something, let me know if this is an old
> subject, or if the Govt. HAVE tried to stop it.
>
> As I explore further I understand the need for thorough analysis of an
> algorithm to see if it is "secure" etc, but I wonder why the Govt. readily
> allows people to pull apart their crypto work without so much as a
complaint??
>
> This is, of course, assuming my question is not the complete stupid
> ramblings of a newbie, but if it isn't, I would like to be enlightened.
>
> PS. Merry Christmas to all, and a SAFE and Happy New Year !!!
>
>
> Cheers!
> Mark Harrop
> [EMAIL PROTECTED]<mailto:>
------------------------------
From: Bob <[EMAIL PROTECTED]>
Subject: Distributing private keys on the internet
Date: Wed, 27 Dec 2000 14:59:38 GMT
Is anyone in this newsgroup paranoid about distributing private keys
over the Internet?
Assume the following:
1. A 3rd party is posing as a customer.
2. This party has the capability to eavesdrop on ALL packets
originating from a secure source and going to other legitimate
customers. This includes packets containing private keys. This 3rd
party has done his homework and knows all of the servers used by the
source and is passively listening to all packets sent by all servers 24
hours a day, 7 days a week.
3. The 3rd party has the capability to debug and analyze the client
software that stores the keys so that a key cracking program can be
easily written.
Based upon these assumptions, it seems to me that there is no possible
method that could be employed to securely distribute a private key over
the Internet.
The safest method of distributing a private key is to have an
individual from the source load the key in person at each client's site.
The second safest method would be to load each client's private key on
a floppy and snail-mail it to each client.
Does anyone have any ideas on how a private key can be securely
transmitted over the Internet when 3rd parties are listening and have
access to the programs that load the keys?
Bob
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Robert Harley <[EMAIL PROTECTED]>
Subject: Re: ___(WANTED) UPDATED performance figures of elliptic curve
multiplications
Date: 27 Dec 2000 16:13:57 +0100
kctang <[EMAIL PROTECTED]> writes:
> I am looking for _UPDATED_ performance figures of elliptic curve
> multiplications for bit lengths range from 150 bits to 300 bits.
>
> My primary interest is on _SOFTWARE_ EC multiplications, though
> hardware results are also much desirable.
>
> It should be of value to have a list of _UPDATED_ EC multiplication
> timings results over
>
> o GF(p),
> o GF(2^n) using polynomial basis,
> o GF(2^n) using optimal normal basis,
> o GF(p^n),
Stick to GF(p) and GF(2^n) with polynomial bases. Normal bases are
slow. GF(p^n) may not be secure.
Here are some times for field multiplications in GF(2^n) on a 750 MHz
Alpha in microseconds:
n time
163 0.48
193 0.64
239 0.92
Who needs dedicated hardware with software this fast? =:^)
In this case, an elliptic curve multiplication takes six field
multiplications per bit (and some cheap stuff: four squares, three
sums) using Peter Montgomery's trick. Count seven multiplications per
bit and you won't be far off.
Bye,
Rob.
.-. [EMAIL PROTECTED] .-.
/ \ .-. .-. / \
/ \ / \ .-. _ .-. / \ / \
/ \ / \ / \ / \ / \ / \ / \
/ \ / \ / `-' `-' \ / \ / \
\ / `-' `-' \ /
`-' http://www.xent.com/~harley/ `-'
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Distributing private keys on the internet
Date: Wed, 27 Dec 2000 15:36:01 GMT
Bob wrote:
>
> Is anyone in this newsgroup paranoid about distributing private keys
> over the Internet?
>
> Assume the following:
>
> 1. A 3rd party is posing as a customer.
>
> 2. This party has the capability to eavesdrop on ALL packets
> originating from a secure source and going to other legitimate
> customers. This includes packets containing private keys. This 3rd
> party has done his homework and knows all of the servers used by the
> source and is passively listening to all packets sent by all servers
> 24 hours a day, 7 days a week.
>
> 3. The 3rd party has the capability to debug and analyze the client
> software that stores the keys so that a key cracking program can be
> easily written.
1 and 2 are feasible, but although the 3rd party might have the
capability to decompile and analyze the client software, that doesn't
mean that the keys can be cracked, unless they're actually seen.
> Based upon these assumptions, it seems to me that there is no possible
> method that could be employed to securely distribute a private key
> over the Internet.
There are a number of methods which can be used, though most require
that only passive eavesdropping by the 3rd party is possible.
1) Connect to the server, and use the Diffie-Helman method to create a
shared secret. From now on, this is the secret key. The protocol is
vulnerable to a MITM attack, but since a seperate key would be
established with the client and server, the attacker would have to
intercept all following sessions to avoid being noticed.
2) Generate a public key/private key pair. Connect to the server, and
send it your public key. The server uses this public key to encrypt the
shared secret, and sends it to the client. This, too, is vulnerable to
a MITM attack, but worse, the 3rd party only needs to be active in it's
interception of the first communication, and can eavesdrop passivly on
all following coummincations
3) A small, text, shared is sent using some non internet method
(registered mail, face-to-face conversation etc) and a protocol like SRP
is used (once!) to create a larger shared secret, which is then stored
and used for all future communications. The short secret can then be
forgotten.
> The safest method of distributing a private key is to have an
> individual from the source load the key in person at each client's
> site.
>
> The second safest method would be to load each client's private key on
> a floppy and snail-mail it to each client.
>
> Does anyone have any ideas on how a private key can be securely
> transmitted over the Internet when 3rd parties are listening and have
> access to the programs that load the keys?
--
Power interrupts. Uninterruptable power interrupts absolutely.
[Stolen from Vincent Seifert's web page]
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Steganography using text as carrier
Date: Wed, 27 Dec 2000 15:40:23 GMT
In article <92bh9l$au6$[EMAIL PROTECTED]>,
AllanW <[EMAIL PROTECTED]> wrote:
> >
> > the security depends only on the agreement of the initial
> > carrier text,
> >
> > {ideally, as random as possible, and changed after each message,
with
> > the instructions for the next carrier text to be used, included in
the
> > previous message,
>
> Please, do not habitually use each message to give instructions for
> the next carrier text to be used. If you do this, then if even ONE
> message is dropped or cannot be decrypted, you are left with no
> communication at all until some manual step is taken.
>
> A variation can be made to work. Alice sends Bob a message, and at
> the end she says "next message will be encoded using Shakespere's
> Taming Of The Shrew." If Bob acknowledges Alice's message before
> Alice sends her next message, she should use Taming of the Shrew.
> But if Alice hasn't received an acknowledgement yet (perhaps she's
> writing to say, "Hey, did you get my message?") then she continues
> to use encoding schemes previously agreed-to.
you are right.
Bob and Alice can keep copies of the previous carrier texts (encrypted
to their satisfaction) to do what you suggest, so that if Alice sends
Bob a reply using the old carrier text, Bob can assume that Alice has
not yet received the new e-mail with the instructions, and so Bob will
re-send the e-mail text with instructions for the new carrier text.
Not using a new carrier text leaves the messages somewhat vulnerable to
character frequency analysis (more as more messages are used with the
same carrier).
The instruction for the new carrier text would not be simply
"page x of Taming of the Shrew as the next carrier text", but
"here is the mpi to use on page x of Taming of the Shrew to convert it
into a random carrier text to be used for the next message"
vedaal
Sent via Deja.com
http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED] (Steve K)
Subject: Re: Distributing private keys on the internet
Date: Wed, 27 Dec 2000 15:50:19 GMT
=====BEGIN PGP SIGNED MESSAGE=====
On Wed, 27 Dec 2000 14:59:38 GMT, Bob <[EMAIL PROTECTED]>
wrote:
>Is anyone in this newsgroup paranoid about distributing private keys
>over the Internet?
Probably not. The whole point of asymmetric ciphers is that it's
safe to distribute public keys publicly. Unless someone has made a
completely unexpected breakthrough that allows them to factor the
product of two large (*very* large) prime numbers, public key crypto
is highly secure. The largest risk in public key encryption is that
the machines it is used on generally have network connections and may
be vulnerable to electronic break-ins.
Knowing this gives the attacker no advantage, but allows anyone to
send plaintext down a one-way hole that only I can extract if from:
- - -----BEGIN PGP PUBLIC KEY BLOCK-----
Version: RSA 2048 Expires: 5/15/01
mQENAzkdmSkBbwEIAMc7Pqi2SfXqphS5Wi/WOeoMgCohSxvairH7xOvKUd2hL4yq
z6XPZVpFoA3H5Qwi1L2kGn7GO5yk6PvRwEf4DN37avC/rQlc7ZyVBc8K7NsK3ktE
f6hgk+SHHud1vPsbClDmdgnCQRTY6HiG4zcrZdtbAp3CQCIMeTAWraPevAdZ2wT5
wx5ydFnp9InA1ZA2XA/Fny96iqvhVSJXj6gXlu5uIB7+DL/Wvw6VAJZG5Gm/PoyX
JThv4j/ZJLrjpeN52aHhgWGLcxi/aa6jdQJIW9C6Hf/Ga9iBADGzhV1gq00ennAW
McXbtkyWPQJwQnld3lp8JWhCemx3xdM4uUkS1eUABRG0JlN0ZXZlbiBGLiBLaW5u
ZXkgPHN0ZXZlMTBrQG1waW5ldC5uZXQ+iQEVAwUQOR2ZKcXTOLlJEtXlAQGtXQf+
Mx+xUB9bCosSflKr3BAtRi9v1Y60vNILrFl0X/haDgIQCevvCpV8op0ADxnXVWUN
rnNiLdAl5acVwsFZ2K84OOdEyKD+ttBIiqlNMchtZmddD0R2j6hiSuSPtmvlRouS
vJTiIlot04Gqk0g5LfYIjDQIE5Kwwl+2PlR2j9OW6w1SREzRKqB5K1McbL4TblGW
0MjnIjz3/fbrxQes3eA3i4BuLBGPfzDLURk6epp6tl492675NGOW0B3zYtTHI85H
sjVDzLIgU3arOpd0NUfElltHHuyOrKXY41smHzdMmA4mxwaO6FSvGFK7ZIcV6IAV
LQaaH3WBtNaS6Z2XY0NYVA==
=Mpdc
- - -----END PGP PUBLIC KEY BLOCK-----
I like that.
:o)
Steve
=====BEGIN PGP SIGNATURE=====
Version: PGPfreeware 6.5.8 for non-commercial use <http://www.pgp.com>
iQEVAwUBOkoPmMXTOLlJEtXlAQErjQgAqM/tG7HuFimG5uMhISEpMFcSKWcyr1Pm
/y03WBzlfToxtVolZz89fEi10iJsYuQDtFpu3qXCTZEBkoBH7+mUHgXkmtURR3Cs
s6kOfqeLBgx+6Cl33k3vx5HGAUDMiUGW/0HTlI6/1KectR2DSM+h0begKSaiyEdt
si02nn9YXVvFnLVRXNQUZJ4FA0BNNh1EOk7DDSx+N4ZqVH/XMarac5TRb6wX/+g0
Z3jWfRVl6NAxtgxSItEoXXN8hlV5REahf1Br0ybBKZb/tCUofp3Vde71zQ3587L9
sLJXvS3ndwfnFn/xbj3uNRfAMbz4/JZQlC2Bv7g52WjqO/OHLrU0Rg==
=lnzy
=====END PGP SIGNATURE=====
---Support privacy and freedom of speech with---
http://www.eff.org/ http://www.epic.org/
http://www.cdt.org/
PGP keys:
RSA - 0x4912D5E5
DH/DSS - 0xBFCE18A9
------------------------------
From: "Jesper Stocholm" <[EMAIL PROTECTED]>
Subject: ECDSA: adding the Point P with -P and restrictions of a & b
Date: Wed, 27 Dec 2000 17:15:51 +0100
I am looking at the math defining ECDSA and there are a couple of things, I
really don't get:
1.
What causes the retriction of a and b to be 4a^3+27b*2 != 0 mod p ? What is
the effect of this ?
2.
When adding a point p with it's negative -p, ecdsa states, that
P+ -P = (x,y)+(x,-y) = O ... but as far as I can see, this only holds for
curves, that are symmetric arround the x-axis ... what if this wasn't the
case ?
Thanks.
Jesper Stocholm
Technical University of Denmark
------------------------------
From: Bob <[EMAIL PROTECTED]>
Subject: Re: Distributing private keys on the internet
Date: Wed, 27 Dec 2000 16:32:13 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Steve K) wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
>
> On Wed, 27 Dec 2000 14:59:38 GMT, Bob <[EMAIL PROTECTED]>
> wrote:
>
> >Is anyone in this newsgroup paranoid about distributing private keys
> >over the Internet?
>
> Probably not. The whole point of asymmetric ciphers is that it's
> safe to distribute public keys publicly. Unless someone has made a
> completely unexpected breakthrough that allows them to factor the
> product of two large (*very* large) prime numbers, public key crypto
> is highly secure. The largest risk in public key encryption is that
> the machines it is used on generally have network connections and may
> be vulnerable to electronic break-ins.
>
> Knowing this gives the attacker no advantage, but allows anyone to
> send plaintext down a one-way hole that only I can extract if from:
>
Well, I don't have a problem with public keys. Its the private keys.
How do you send a private key securely over the Internet if a 3rd party
is listening to everything you send and has your client software along
with a good debugger that allows him to easily write a private key
cracking program?
I don't think private keys are safe to transmit over the Internet.
Please, somebody tell me I'm wrong. I would love to be wrong...
Bob
Sent via Deja.com
http://www.deja.com/
------------------------------
From: "Wei Kok Ng" <[EMAIL PROTECTED]>
Subject: Block or stream cipher
Date: Thu, 28 Dec 2000 00:53:27 +0800
Hi,
I would like to know how you would decide whether to use a stream or a block
cipher. In what situation would a stream cipher be more preferable than a
block cipher and vice versa.
Thanks in advance.
W.K. Ng
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: ECDSA: adding the Point P with -P and restrictions of a & b
Date: Wed, 27 Dec 2000 16:51:11 GMT
In article <92d4kp$3o0$[EMAIL PROTECTED]>,
"Jesper Stocholm" <[EMAIL PROTECTED]> wrote:
> I am looking at the math defining ECDSA and there are a couple of
things, I
> really don't get:
>
> 1.
> What causes the retriction of a and b to be 4a^3+27b*2 != 0 mod p ?
The curve becomes singular; you no longer have an elliptic curve if p
divides the discriminant.
> 2.
> When adding a point p with it's negative -p, ecdsa states, that
>
> P+ -P = (x,y)+(x,-y) = O ... but as far as I can see, this only holds
for
> curves, that are symmetric arround the x-axis ...
No. It holds for all curves. O is the group identity. P + O = P,
hence P + (-P) = 0 for all P. Symmetry about the x-axis is irrelevent.
--
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/
------------------------------
** 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
******************************
