Cryptography-Digest Digest #327, Volume #14 Thu, 10 May 01 10:13:00 EDT
Contents:
Re: A simple encryption algorithm based on OTP ("Tom St Denis")
Re: Probablistic Algorithms For Square Roots of QRs in Z/n (Tim Tyler)
Re: Random and not random (Mok-Kong Shen)
Re: Weird Rijndael test vectors wanted ("Brian Gladman")
Re: Weird Rijndael test vectors wanted ("Brian Gladman")
Re: Are low exponents a problem with RSA? (DJohn37050)
Re: Are low exponents a problem with RSA? (DJohn37050)
Re: Crypto web-page (Mark Wooding)
Re: Best, Strongest Algorithm (SCOTT19U.ZIP_GUY)
Re: Integrity check algorithm (Vincent Quesnoit)
Re: Probablistic Algorithms For Square Roots of QRs in Z/n (Don Leclair)
Re: enumerating permutations (SCOTT19U.ZIP_GUY)
Re: new encryption idea ("G. Orme")
Re: Looking for a simple code wheel to print out for kids (John Myre)
Re: Best, Strongest Algorithm (jlcooke)
----------------------------------------------------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: A simple encryption algorithm based on OTP
Date: Thu, 10 May 2001 11:13:57 GMT
" invisible inkie" <[EMAIL PROTECTED]> wrote in message
news:9ddsje$7q3$[EMAIL PROTECTED]...
> <delurk>
>
> "Tom St Denis" dropped into the real world with a crash and proclaimed...
> >
> > "Siva Prasad Gummadi [T]" <[EMAIL PROTECTED]> wrote in message
> <snip>
> >
> > Wow you're the first person to think of a "STREAM CIPHER". I suggest
you
> > read some texts on crypto before declaring yourself the next Marlyn Vos
> > Savant...
>
> And I suggest you read some texts on social skills before dealing with
> people again!
>
> I respect your knowledge a lot, Tom, and I'm the first to admit that
> I eagerly read your posts, because I learn a lot from them, but every
> now and then I blow my top at your way of posting!
Oh thanks. I post to share knowledge and learn at the same time. I hope
you keep reading my posts (see below)
> Siva was proposing something, and compared to other people who
> are new here, he described it pretty seriously. He said "I think"
> where others would've written "I know" without doing so. He didn't
> declare himself anything, he didn't claim he'd found a golden rule,
> he just asked for feedback, and he did it politely, ferchrissake!
>
> Easy on the lemming, Tom, not everyone is (yet) as knowledgeable
> as you are! Give them some time and, what I as a teacher think even
> more important, patience and respect. Their points might be as valid
> as yours.
You're right, people skills is not my thing. And I am always trying to be
modest since if I ever claimed I knew everything I wouldn't need to post
here!
To Siva: Sorry I didn't mean to come off rude. No hard feelings?
My original suggestion stands. I am not trying to be mean but if you want to
be half way competent you have to read some text either AC2 or HAC.
Otherwise you will be blundering in the dark (much like I was when I started
posting here in 1998) and generally just getting more frustrated.
Tom
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Probablistic Algorithms For Square Roots of QRs in Z/n
Reply-To: [EMAIL PROTECTED]
Date: Thu, 10 May 2001 11:29:30 GMT
Tim Tyler <[EMAIL PROTECTED]> wrote:
: Jeffrey Walton <[EMAIL PROTECTED]> wrote:
: : Anyone have a heuristic or probabilistic Algorithm?
: http://www.azillionmonkeys.com/qed/sqroot.html has some useful algorithms,
: including some pretty rough-and-ready ones.
...but they tend to deal with integers - sorry - my newsreader only shows
me the first n characters of the subject line by default...
--
__________ http://rockz.co.uk/ http://alife.co.uk/ http://hex.org.uk/
|im |yler http://atoms.org.uk/ http://mandala.co.uk/ [EMAIL PROTECTED]
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Random and not random
Date: Thu, 10 May 2001 13:43:40 +0200
I like to post the following revised version of my
argumentation sent this morning, partly as a result of the
valuable comments received from Bryan Olson, and hope that
it could eventually stand a second wave of comments and
critiques.
Let's denote with U the original and perfect strategy of
choosing the permutation, where, in order to ensure absolute
no dependency on the content of the OTP segements, I
additionally employ a perfect die to determine the
permutation to be used, thus avoiding any conceivable
human bias. Let the die be denoted by the ideal random
variable r1. Under U, each and every message being transmitted
enjoys the perfect security property as defined by Shannon.
Now I devise a second strategy V of choosing the permutation
in that I carefully examine the pad (the 3 segments) every
time and with that information determine (according to a
certain algorithm designed by me) which permutation to choose.
We denote this choice by the variable r2, which is in general
at best a more or less good pseudo-random variable, since
factors of human decision etc. are involved, i.e. it is not
an ideal random variable. (The theoretical case that r2 is
also an ideal random variable can in fact be excluded for the
purpose of the present discussion, because we would then have
a situation where, despite dependency on the content of the
OTP segments (which is the very cause to be investigated here
for its possible influence on the loss of perfect security
of OTP processing), the result of encryption would have been
as perfect as the original genuine OTP processing.) Now,
according to what a number of discussion partners in this
thread have maintained up till now, the perfect security of
OTP is no longer existent with the strategy V, for the choice
of permutation depends (in fact rather strongly depends) on
the content of the OTP segements. To be precise, the opponent
now can gain some information (in comparison to the definition
of perfect security) in a certain fraction of the total number
of messages intercepted. We denote this fraction by the
non-zero number P and designate it (only for our purpose) as
the 'damage coefficient'. (Thus by definition the damage
coefficient under U is zero, since all messages transmitted
enjoy perfect security.) Note however that under U one of the
6 possible permutations is chosen by the ideal random variable
r1, while under V a permutation (in the same set of 6) is
chosen by the non-perfect variable r2. Thus there is a certain
non-zero probability Q with which the selection of U and the
selection of V coincide, in which case the opponent will
receive under both strategies identical blocks of bits, the
messages being permuted identically. Therefore, there should
be under U a non-zero damage coefficient of P*Q, which is
contradictory to the fact that, by definition, it should
have been zero.
M. K. Shen
================================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: "Brian Gladman" <[EMAIL PROTECTED]>
Subject: Re: Weird Rijndael test vectors wanted
Date: Thu, 10 May 2001 12:56:53 +0100
"Mark Wooding" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Simon Josefsson <[EMAIL PROTECTED]> wrote:
>
> > Do you get these values? I do, but I just added Nk={5,7} support to
> > my implementation so it's not verified to be correct. (Nb=4)
> >
> > KEY=0000000000000000000000000000000000000000
> > PT=00000000000000000000000000000000
> > CT=32CB23EE8DEBD0D4E0983EE4D3318A5F
> >
> > KEY=00000000000000000000000000000000000000000000000000000000
> > PT=00000000000000000000000000000000
> > CT=BE47C9BF5D104A8EC32A13C94596237C
>
> No. I get neither.
>
> I've managed to get the reference implementation and mine to agree, but
> it took a lot of hard work and headscratching. (There are lots of
> switch statements to work out numbers of rounds and whatever, and the
> key schedule is just wrong for Nk = 7.) I'm still not convinced I'm
> right, and would like independent confirmation.
>
> I now get these test vectors:
>
> KEY=0000000000000000000000000000000000000000
> PT=00000000000000000000000000000000
> CT=94B434F8F57B9780F0EFF1A9EC4C112C
>
> KEY=0000000000000000000000000000000000000000000000000000000
> PT=00000000000000000000000000000000
> CT=73F8DFF62A36F3EBF31D6F73A56FF279
>
These values are correct, the earlier ones quoted are wrong.
Brian Gladman
------------------------------
From: "Brian Gladman" <[EMAIL PROTECTED]>
Subject: Re: Weird Rijndael test vectors wanted
Date: Thu, 10 May 2001 12:54:51 +0100
"Mark Wooding" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Simon Josefsson <[EMAIL PROTECTED]> wrote:
>
> > Do you get these values? I do, but I just added Nk={5,7} support to
> > my implementation so it's not verified to be correct. (Nb=4)
> >
> > KEY=0000000000000000000000000000000000000000
> > PT=00000000000000000000000000000000
> > CT=32CB23EE8DEBD0D4E0983EE4D3318A5F
> >
> > KEY=00000000000000000000000000000000000000000000000000000000
> > PT=00000000000000000000000000000000
> > CT=BE47C9BF5D104A8EC32A13C94596237C
>
> No. I get neither.
>
> I've managed to get the reference implementation and mine to agree, but
> it took a lot of hard work and headscratching. (There are lots of
> switch statements to work out numbers of rounds and whatever, and the
> key schedule is just wrong for Nk = 7.) I'm still not convinced I'm
> right, and would like independent confirmation.
>
> I now get these test vectors:
>
> KEY=0000000000000000000000000000000000000000
> PT=00000000000000000000000000000000
> CT=94B434F8F57B9780F0EFF1A9EC4C112C
>
> KEY=0000000000000000000000000000000000000000000000000000000
> PT=00000000000000000000000000000000
> CT=73F8DFF62A36F3EBF31D6F73A56FF279
These values are correct, the earlier ones are wrong.
Brian Gladman
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Date: 10 May 2001 12:10:15 GMT
Subject: Re: Are low exponents a problem with RSA?
See Dan Boneh on why low exponent RSA appears to NOT be equivalent to
factoring. RSA itself is not known to be equivalent to factoring, but low
exponent RSA may be a concern if you want to have the most assurance that a bad
guy will need to factor your modulus (or equivalment work) to break it.
Don Johnson
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Date: 10 May 2001 12:14:41 GMT
Subject: Re: Are low exponents a problem with RSA?
There are a few reasons to be concerned with using low exponent RSA.
1) When using 3, the top HALF of the private key d is revealed, this is not a
problem in and of itself but might be combined with another attack such as
timing and allow the timing attacker to synchronize based on known values.
2) As mentioned elsewhere, if you send the same message to the number of
parties >= public exponent, you need to ensure that the messages are different
in appearance.
3) Use of a larger exponent could be considered insurance against the
possibility of an RNG failure during formatting of the message.
Don Johnson
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Crypto web-page
Date: 10 May 2001 12:45:41 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
> "Widespread use of the RSA public-key algorithm, when there are superior
> alternatives. "
>
> Which is stupid since RSA has yet to be broken and RSA is far simpler then
> "surperior" algorithms
The underlying theory is, admittedly, simple.[1] But there's lots of
weird special cases and strange things you have to do with RSA --
padding systems like PKCS#1 or OAEP or PSS, knowing what sizes of
exponent to use, etc. So I dispute that RSA is actually `far' simpler
than other algorithms.
Even elliptic curve crypto can be considered to be on the same level of
complexity. You have to implement the maths, and it's a bit weird in
places, but you have to implement the maths for RSA too (including
strange things like sliding-window exponentiation and Montgomery
reduction). Yes, there are bad types of curves, but you can avoid them
by just using off-the-shelf curves from OAKLEY or FIPS 186-2.
[1] I think that Diffie-Hellman (and hence ElGamal) is actually
conceptually simpler, and that Diffie-Hellman is actually better in
many protocols because it can provide perfect forward secrecy much
more cheaply.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Best, Strongest Algorithm
Date: 10 May 2001 12:54:22 GMT
[EMAIL PROTECTED] (Joseph Ashwood) wrote in <e7IilJM2AHA.196@cpmsnbbsa07>:
>"jlcooke" <[EMAIL PROTECTED]> wrote in message
>news:[EMAIL PROTECTED]...
>> Algorithms using keys larger than the block sizes provide the
>> existence of the following relationship:
>>
>> C = cipher text
>> P = plain text
>> K = key
>>
>> If length(Ki) == 256 while length(Pi) == length(Ci) == 128 (as in
>> AES256)
>>
>> There are 2^256 possible keys, and only 2^128 transformations from any
>> P_i to C_i.
>
>What you're trying to say is for all (C,P) pairs there exist an average
>of 2^128 K that will map the two of them. This is a deceptive figure.
>The valid number if to compare 2^128! to 2^256. The space used in the
>cipher is minute compared to the space of permutations, so much so that
>56! is slightly larger than 2^256, meaning that a 256-bit key is the
>optimal choice for 56-value encryption in order to choose each
>permutation. This can be easily extrapolated to see that 256-bits is far
>from too large for a 128-bit block.
>
>> So I
>> agree with Scott in saying - basiclly - encryption really mangles data
>
>That's where you're wrong, that view of encryption if not usable at the
>level of this newsgroup (it is however useful when talking to the
>completely uninitiated), at the level of this newsgroup they are
>selections of permutations so to be used for a substitution. The
>strength of the selected permutations is the interesting factor, as well
>as the speed of computing the location in the table that is of interest.
>
Lets clear this up since Joe may have complicted it.
even a 19bit block size would need a key of over a million
bytes. to represent all the possible transforms. In scott19u
for example the true key over a million bytes long. The
reason its hard to break is that it hard to find any input
output pairs for the 19 bit blocks used.
If one is going to use a cipher of 128 bits for a block
size. Then the number of transforms possible becomes
(2**128)! this is a huge number compared to a small key
of 256 bits which allows for only 2**256! possible transformations.
so any block cipher using a 128 bit block and only a 256 bit key
can not be very complex. And for a given method with a small
key of 256 bits. It would not take very many pairs of cipher text
to plain text to mathemtically have enough information to determine
the key. A place like the NSA would only need a few pairs to uniquely
show which Rijndeal key was used. It would be foolish for them
not to build custom hardware to do this.
in the case of BICOM
followed by reverse and
then BICOM again.
for a totally bijective
compression encryption.
It would be extremely hard to get any pairs of data for
such a machine. It would be hard to get data for any special
sequence as could have been used in a counter mode where
a relationship to sucessive pairs could be used. Thats way
using Rijndeal in the way I mentions would be far more secure
your would have a much stronger encryption based on the whole
file as a blocksize and a 512bit key. If there is such a
thing is measureable secruity for Rijndael the double BICOM
system would an order of magnitude more secure.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
http://www.jim.com/jamesd/Kong/scott19u.zip
My website http://members.nbci.com/ecil/index.htm
My crypto code http://radiusnet.net/crypto/archive/scott/
MY Compression Page http://members.nbci.com/ecil/compress.htm
**NOTE FOR EMAIL drop the roman "five" ***
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged or
something..
No I'm not paranoid. You all think I'm paranoid, don't you!
------------------------------
From: Vincent Quesnoit
Subject: Re: Integrity check algorithm
Date: Thu, 10 May 2001 14:27:56 +0200
Reply-To: [EMAIL PROTECTED]
Uros Podlogar a écrit :
> I read about RSA and if I understand correct there is quite opposite. You
> encode the message with public key, but you can decode this message only
> with private key. I would like to encode message with private key and then
> decode this message with public key. With this function everybody could
> check message integrity, but no one could generate new message.
>
> Regards
>
> Uros
>
RSA can be used the other way around : you decode a digest of your message with
your private key, send this as the integrity check. To check integrity, one
simply encodes the digest using the public key and checks it against the digest
of the message
Regards
Vincent
------------------------------
From: Don Leclair <[EMAIL PROTECTED]>
Subject: Re: Probablistic Algorithms For Square Roots of QRs in Z/n
Date: Thu, 10 May 2001 13:03:07 GMT
>Anyone have a heuristic or probabilistic Algorithm?
As a previous poster remarked, there are fast algorithms when working a field of
prime order. If the order is composite you have to factor it.
For square roots in Z/p the Tonelli-Shanks algorithm is the best I've used.
Search on Google for "tonelli shanks".
It's probabilistic in that you have to find a quadratic nonresidue by guessing
and calculating the Legendre symbol. In practice only a few tries are required.
I have implemented it and it is very fast. The search on Google should turn up
pseudo-code and/or source.
Don Leclair
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: enumerating permutations
Date: 10 May 2001 13:00:13 GMT
[EMAIL PROTECTED] (Tim Tyler) wrote in <[EMAIL PROTECTED]>:
>Tom St Denis <[EMAIL PROTECTED]> wrote:
>
>: I got bored in my College "Technical Math" class so I think I came up
>: with a way to enumerate permutations [...]
>
>The conventional way to number permutations is to put them into
>lexicographic order. There's and existing algorithm to iteratively
>generate permutations in this order.
>
>The algorithm is described in: E. W. Dijkstra, A Discipline of
>Programming, Prentice-Hall, 1976, p.71.
>
>There's an implementation with source code in an applet on one of my
>pages:
>
> http://mandala.co.uk/permutations/
Actaully if Tom looks at the code for scott16u I have to deal with
permutations. You cam look at the table as a shuffling of a deck
of cards wiht 2**16 cards. the key is sort of the index to the
permustion used. If you look at the code it not that hard to generate
a unqiue number that stands for each permutaion.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
http://www.jim.com/jamesd/Kong/scott19u.zip
My website http://members.nbci.com/ecil/index.htm
My crypto code http://radiusnet.net/crypto/archive/scott/
MY Compression Page http://members.nbci.com/ecil/compress.htm
**NOTE FOR EMAIL drop the roman "five" ***
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged or
something..
No I'm not paranoid. You all think I'm paranoid, don't you!
------------------------------
From: "G. Orme" <[EMAIL PROTECTED]>
Subject: Re: new encryption idea
Date: Thu, 10 May 2001 13:35:48 GMT
G. Thanks for the feedback. The idea is very basic and depends on whether
there is a group of algorithms that would be secure. I think if the input
and output are relatively prime to each other this would be important. The
main protection might be the size of the random numbers inputted as to how
well they would make the algorithm. Has the random number input idea been
done before?
"Roger Fleming" <[EMAIL PROTECTED]> wrote in message
news:3af15ccc$0$25510$[EMAIL PROTECTED]...
> "G. Orme" <[EMAIL PROTECTED]> wrote:
> > This is just an idea that will probably be flawed at this stage, but
it
> >seems like a different approach. The idea is that one must guess an
> >encrypting algorithm instead of a password.
>
> Umm, actually people have suggested that, and it has been generally
regarded
> as too inconvenient for practical use, and too difficult to analyse the
> security. There are some who support the idea, umm, possibly Terry Ritter?
>
> > Here is a basic example. Say you are encrypting some text. Letters
are
> >denoted as numbers a=1 to z=26, or some other combination. One has an
> >equation which on inputting the letter's number (e.g. c=3) outputs a
number
> >which is the encryption of the letter, called here the output (this
number
> >would be very large). As an illustration say the minimum difference
between
>
> Up to the very large, so far this was a pretty general definition of ANY
> character oriented cipher. The "very large" means there will necessarily
be
> data expansion, ie the ciphertext will be much longer than the plaintext.
In
> some situations this may not matter too much, but in many electronic
> applications it is unacceptable.
>
> >any output is a billion or more. That is, no encrypted number
representing a
> >letter is closer than a billion to any other. As an additional
enhancement
> >one could have it so the algorithm changes sequentially after encrypting
> >each letter in a preagreed way so that for example all the "e"'s wouldn't
be
> >the same number. For example one algorithm encrypts the first letter,
> >another encrypts the second letter, and so on. The algorithm could change
in
> >a way that is itself algorithm based. Instead of sending a new password
one
> >would send a new algorithm.
>
> This algorithm changing is very complicated and inefficient (of time and
> memory) to arrange in practice, unless the "new" algorithm can be
specified by
> a simple parameter. That, of course, is esentially what a key does.
>
> > There would also be an additional input of for example random numbers
> >which can alter the encrypted output number by say plus or minus a
million.
> [...]
>
> Well, the example as stated is a bit vague. I can think of a totally
insecure
> algorithm that meets this specification:
> c = 1000000000 x p + 10000000 x n + 1000000 x r
> where c is ciphertext, p is plaintext (values 1 .. 26), n is position in
> stream, and r is randomly either -1 or 1
> But
> c = E( n || p || 0 || 0) + 1000000 x r
> where E is any good block cipher and || denotes concatenation, also meets
the
> definition (well, with high probability), but is pretty secure.
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Looking for a simple code wheel to print out for kids
Date: Thu, 10 May 2001 07:40:54 -0600
Ed Pugh wrote:
<snip>
> This is for kids around ages 7-12 or so, so it should not be
> too fancy or complicated.
<snip>
I seem to recall something about "secret codes" in one of the Cub
Scout books. I know there is a lot of stuff on scouting on the web.
Maybe a Google search will turn something up, or maybe there's a
scout shop near you.
(My own sons got most interested when the message had direct
relevance, like encoding their own names. The theory didn't seem
to be interesting to them, but the idea of secret communication
was. I suppose you could pre-encode some clues to finding a
"treasure", like chocolate coins, or have them exchange messages.)
Good luck.
JM
------------------------------
From: jlcooke <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm
Date: 10 May 2001 13:55:45 GMT
Doug Kuhlman wrote:
> False. There are (2^128)! (yes, 2^128 factorial) transformations (maps)
> from P to C, if both are of size 128 bits. That is significantly more
> than merely 2^256.
Pardon. Every time I find myself writing to a news group like sci.crypt
I find myself wishing I had taken a few english courses.
For a _single_ given P, there are 2^128 possible transformations into C
since there are 2^128 possible C_i's. ALL transformations (from all
possible P_j's to all possible C_i's) are the order of (2^128)! as Doug
corrected me.
JLC
------------------------------
** 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
******************************
