Cryptography-Digest Digest #175, Volume #12 Fri, 7 Jul 00 14:13:00 EDT
Contents:
Re: Information-theoretic hash question (was Re: CRC question) ("Scott Fluhrer")
Re: Has RSADSI Lost their mind? (DJohn37050)
Re: Has RSADSI Lost their mind? (Mark Wooding)
Re: DES Analytic Crack (Volker Hetzer)
Re: Prime Numbers? (Quisquater)
Re: A variation of the Hill cipher (Nicholas Hopper)
Re: Quantum Computing (Was: Newbie question about factoring) (Jeff Erickson)
Re: A variation of the Hill cipher (Mok-Kong Shen)
Re: SafeIT - Untrusted encryption program. (Mark Wooding)
Re: Prime Numbers? (Florian Weimer)
Re: A variation of the Hill cipher (Mok-Kong Shen)
computer program: extract consonants/vowels from input (Jeff Mullen)
Re: Prime Numbers? (Quisquater)
----------------------------------------------------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Information-theoretic hash question (was Re: CRC question)
Date: Thu, 6 Jul 2000 18:40:22 -0700
Benjamin Goldberg <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Hmm, what if I change it to bitlength(M) strictly-less-than 2**N, rather
> than less-than-or-equal ? Or do I have to use 2**(N-1) for it to work?
For hamming distance of 2, yes, that works. An N-bit CRC will always detect
a 1 or 2 bit difference for bitlength < 2**N if (and only if) that CRC was
based on a primitive polynomial.
For hamming distance of up to 3, an N-bit CRC can detect that different for
bitlength < 2**(N-1) if that CRC is the (x+1) polynomial multiplied with an
N-1 degree primitive polynomial (which is how most standard CRC polynomial
are generated).
>
> Broadening the question, and asking various permutations:
> 1) What is the maximum hamming distance that two Y-bit messages can
> have, and still have two different X-bit hashes?
> 2) What is the minimum hash size needed to detect differences in Y-bit
> messages which have a hamming distance Z?
> 3) What is the maximum message length for which an X bit hash can detect
> differences between messages which have a hamming distance of Z?
I'll let those be exercises for the reader...
>
> Scott Fluhrer wrote:
> >
> > Benjamin Goldberg <[EMAIL PROTECTED]> wrote in message
> > news:[EMAIL PROTECTED]...
> > > Is it possible, for an N-bit CRC, for any n ( 1 <= n <= N ) 1-bit
> > > changes in a message M ( bitlength(M) <= 2**N ), the output value
> > > changes?
> > No, unless N = 1
> >
> > Consider the 2**N messages consisting of 2**N-1 zeros and a one, and
> > the 1 message consisting of 2**N zeros. There is a total of 2**N+1
> > messages here, and each pair of messages has either 1 bit or 2 bit
> > hamming distance. Since an N-bit CRC has only 2**N possible values,
> > there is a collision in here somewhere.
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: Has RSADSI Lost their mind?
Date: 07 Jul 2000 15:34:41 GMT
Yin is no longer with RSA Security.
Don Johnson
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Has RSADSI Lost their mind?
Date: 7 Jul 2000 15:58:23 GMT
DJohn37050 <[EMAIL PROTECTED]> wrote:
> Yin is no longer with RSA Security.
Oh, fair enough.
-- [mdw]
------------------------------
From: Volker Hetzer <[EMAIL PROTECTED]>
Subject: Re: DES Analytic Crack
Date: Fri, 07 Jul 2000 18:11:01 +0200
"Douglas A. Gwyn" wrote:
>
> Mok-Kong Shen wrote:
> > Do you know any literature about obtaining and solving the set of
> > equations for DES? Could you give any reference or are you merely
> > postulating on a miscalculation? Thanks.
>
> As previously reported here, many years ago a colleague constructed
> the complete, explicit set of DES encipherment equations and printed
> them on a line printer, resulting in output just a few inches thick.
> That much data can easily be held in RAM on today's computers.
The problem is not to hold them in RAM but to solve them.
Suppose you've got Ciphertext=DES(Key,Messagetext).
Now, you've got Ciphertext and Messagetext and want to know
what key was used. You can try to solve the equation for
the key bits or you could try to find bits that make the equation true.
I don't think the first approach is feasible.
However, in the second case a lot of progress has been made lately. Did
anybody try to solve those equations using a BDD approach?
Greetings!
Volker
--
The early bird gets the worm. If you want something else for
breakfast, get up later.
------------------------------
From: Quisquater <[EMAIL PROTECTED]>
Subject: Re: Prime Numbers?
Date: Fri, 07 Jul 2000 18:21:25 +0200
Florian Weimer wrote:
>
> I think the proof is correct, for the following reason: First, show
> that a number is prime if and only if it is not divisible by other
> primes. Under the assumption that n is the largest prime, n! + 1 is
> prime, because no prime numbers (which are in the range 1 .. n) divide
> it. But n! + 1 is larger than n, contradiction.
No! It is only a proof that it is a product of primes greater than n.
See also to see the efforts of factorisation of n! + 1:
http://www.uow.edu.au/~ajw01/ecm/curves.html
========
Universit� de Louvain
UCL Crypto Group
see http://www.dice.ucl.ac.be/crypto
t�l. 32.10.47.25.41 (connected to my voicebox and cellular phone)
fax: 32.2.358.55.83 (only for me)
SMS: send an email (only the subject will be transmitted) to
[EMAIL PROTECTED]
------------------------------
From: Nicholas Hopper <[EMAIL PROTECTED]>
Subject: Re: A variation of the Hill cipher
Date: Fri, 7 Jul 2000 12:43:05 -0400
On Fri, 7 Jul 2000, Mok-Kong Shen wrote:
>
> The Hill cipher (AMM 36 (1929)) is defined by the equation
>
> C = H * P mod u
>
> where H is an invertible matrix in Z_u and P and C are square
> matrices representing a section of the numerically coded
> plaintext and ciphertext message respectively.
>
> Consider the matrix iteration
>
> X_(i+1) = M * X_i mod u
>
> with a matrix M whose main diagonal elements have inverses
>
> Now we can define a variant of the Hill cipher as follows:
> Randomly choose an M (with invertible diagonal elements) and
> select a positive number n. Let X_0 = P. Then C is given by
> the n_th iterate X_n.
Note that X_n = M*(X_{n-1})
= M*(M*X_{n-2})
= M^n * P
i.e., this is exactly the Hill Cipher. (with a restricted keyspace)
Note also that M _must_ be invertible for the inversion process to
succeed (regardless of how it is calculated). Suppose that M is not
invertible. Then there is a non-trivial vector y such that My = 0. Then
for all X, M*(X + [yy...y]) = MX and so every ciphertext will have at
least two valid plaintexts associated with it. For example, suppose that
we use 2x2 matrices:
M = | m1 m2 |
| m3 m4 |
y = | y1 |
| y2 |
My = 0 => m1y1 + m2y2 = 0; m3y1 + m4y2 = 0
X = | x1 x2 |
| x3 x4 |
MX = | m1x1 + m2x3 m1x2 + m2x4 |
| m3x1 + m4x3 m3x2 + m4x4 |
M(X+[yy]) = | m1(x1+y1) + m2(x3+y2) m1(x2+y1) + m2(x4+y2) |
| m3(x1+y1) + m4(x3+y2) m3(x2+y1) + m4(x4+y2) |
= | m1x1 + m2x3 + m1y1 + m2y2 m1x2 + m2x4 + m1y1 + m2y2 |
| m3x1 + m4x3 + m3y1 + m4y2 m3x2 + m4x4 + m3y1 + m4y2 |
= MX
> Note that M is not necessarily invertible. Thus we are more
> flexible in its choice than in the case of H in the original
> scheme of Hill. In particular, if u is a power of 2, which is
> convenient for implementation, one can generate M with a PRNG
> (preferably one M for each P as part of a message), subject
> to the restriction that the diagonal elements be odd. Further,
> analogous to a previous article of mine on the Hill cipher
> posted to sci.crypt, we can also use two M matrices as follows
> to obtain enhanced diffusion effects of the encryption:
>
> X_(i+1) = M1 * X_i * M2 mod u
Again, C = X_n = (M1^n)*P*(M2^n) and both M1 and M2 must be invertible by
the same arguments.
------------------------------
Crossposted-To: comp.theory
Subject: Re: Quantum Computing (Was: Newbie question about factoring)
From: [EMAIL PROTECTED] (Jeff Erickson)
Date: Fri, 07 Jul 2000 16:50:06 GMT
ca314159 <[EMAIL PROTECTED]> writes:
| D. Mermin poses a useful problem for only one qubit:
| to determin the millionth bit of the binary expansion
| of sqrt(2+x). That would be big news.
Hardly. Given the recent computation of the trillionth(!) bit of pi
using classical computers, why should anyone think computing bits of
sqrt(2+x) is hard?
http://www.mathsoft.com/asolve/plouffe/plouffe.html
http://www-stud.enst.fr/~bellard/pi-challenge/announce220997.html
http://www.cecm.sfu.ca/organics/papers/bailey/
--
/"\ Jeff Erickson mailto:[EMAIL PROTECTED]
\ / Computer Science Department http://www.uiuc.edu/~jeffe
\ University of Illinois, Urbana-Champaign
/ \ ASCII Ribbon Campaign for attachment-free news and email
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: A variation of the Hill cipher
Date: Fri, 07 Jul 2000 19:04:50 +0200
Addendum:
I suggested in previous threads in sci.crypt a possibility
of introducing further unknowns (for the cryptanalyst) into
the original (non-iterative) scheme by letting the main
diagonal or both diagonals of P be filled with numbers from
PRNG and only the remaining elements be filled by plaintext.
This is of course also doable with the present iterative
scheme.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: SafeIT - Untrusted encryption program.
Date: 7 Jul 2000 17:02:18 GMT
[EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:
> But the thing that make me want to post this all over sci.crypt is
> that the symmetric key algorithm used in their program are a 'trade
> secret'. Sure it's legal to do so, but not acceptable. The users buy
> the program and thinks it's safe, but it might not. It it's safe,
> prove it!
Having had a look around their web site, there are a few other choice
phrases I picked out from http://www.safeit.com/info/whitepaper.html.
: The SafeIT[tm] Algorithm
:
: * The SafeIT encryption algorithm is a secret key stream block
: cipher.
This is stunning: a `stream block cipher'! Wow! It must be good.
Either that or the writer is hopelessly confused.
: * The algorithm consists of linear and non linear operations which
: are performed in rounds. XOR operations are included in this
: process.
I don't think it would take a genius to guess this. It does illustrate
that the author knows some jargon, though.
: * The algorithm compresses all information that is being encrypted.
Sounds reasonable. So does PGP. But let's see below.
[snip some other points.]
: Characteristics of encrypted information
:
: * Information encrypted by the SafeIT algorithm is always compressed
: to a maximum. There are no known patterns, linearity or symmetries
: to be found in the encrypted information.
A rather bizarre juxtaposition, wouldn't you say? That the plaintext is
compressed should be irrelevant to whether there are observable patterns
in the ciphertext. Or does he have a different definition of
`compression' from the one I'm familiar with?
: * If one bit is changed in the plaintext, the encrypted information
: is a completely changed. If one bit in the encryption key is
: changed, the encrypted information is completely changed.
Errr... this is a standard necessary condition for a good block cipher.
They seem to be claiming it as something special.
: Man in the middle attack
:
: [...] To control this, SafeIT allows you to view encrypted e-mails. If
: two counterparts compare the same encrypted e-mail the content should
: be exactly the same. If so, a "man-in-the-middle" attack has not been
: performed and automatic security has been established correctly. This
: means that the secure connection cannot be attacked.
This is priceless. It's also rubbish. A clever man-in-the-middle can
modify a Diffie-Hellman exchange so that both legitimate parties end up
with the *same* key, but he can easily compute what that key is.
This one looks like a candidate for the Crypto-Gram doghouse.
> I hope they dare to publish their algorithm to the public. Othervice, I
> hope someone else does.
Quite so.
-- [mdw]
------------------------------
From: Florian Weimer <[EMAIL PROTECTED]>
Subject: Re: Prime Numbers?
Date: 07 Jul 2000 19:20:39 +0200
Quisquater <[EMAIL PROTECTED]> writes:
> > I think the proof is correct, for the following reason: First, show
> > that a number is prime if and only if it is not divisible by other
> > primes. Under the assumption that n is the largest prime, n! + 1 is
> > prime, because no prime numbers (which are in the range 1 .. n) divide
> > it. But n! + 1 is larger than n, contradiction.
>
> No! It is only a proof that it is a product of primes greater than n.
Strictly speaking, this is not true. The proof outlined above only
proves that the number of prime elements in Z is not finite. The
problem seems to be that most reasoning is done on the base of a false
assumption, and people tend to think that the consequences of a false
assumption are true if they can be proved using the assumption.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: A variation of the Hill cipher
Date: Fri, 07 Jul 2000 19:41:09 +0200
Nicholas Hopper wrote:
> On Fri, 7 Jul 2000, Mok-Kong Shen wrote:
>
> >
> > The Hill cipher (AMM 36 (1929)) is defined by the equation
> >
> > C = H * P mod u
> >
> > where H is an invertible matrix in Z_u and P and C are square
> > matrices representing a section of the numerically coded
> > plaintext and ciphertext message respectively.
> >
> > Consider the matrix iteration
> >
> > X_(i+1) = M * X_i mod u
> >
> > with a matrix M whose main diagonal elements have inverses
> >
> > Now we can define a variant of the Hill cipher as follows:
> > Randomly choose an M (with invertible diagonal elements) and
> > select a positive number n. Let X_0 = P. Then C is given by
> > the n_th iterate X_n.
>
> Note that X_n = M*(X_{n-1})
> = M*(M*X_{n-2})
> = M^n * P
>
> i.e., this is exactly the Hill Cipher. (with a restricted keyspace)
>From the fact that M is not necessarily invertible (see below) one
sees that the scheme is not identical to the original Hill cipher,
which requires a non-singlular M.
> Note also that M _must_ be invertible for the inversion process to
> succeed (regardless of how it is calculated). Suppose that M is not
> invertible. Then there is a non-trivial vector y such that My = 0. Then
> for all X, M*(X + [yy...y]) = MX and so every ciphertext will have at
> least two valid plaintexts associated with it. For example, suppose that
> we use 2x2 matrices:
[snip]
You seem not to have followed the iteration process involved. The
computation of each single step (updating an element of X) is
reversible. Hence the whole process is reversible. Note that the
receiver does exactly the same steps as the sender, but only in the
reverse order. For simplicity, let me illustrate, instead of with a
square matrix X, with a column vector V and a matrix M of 2*2.
We have, denoting the new values of V with an apostrophe:
v1' = m11*v1 + m12*v2 (1)
v2' = m21*v1' + m22*v2 (2)
On decryption, the receiver first works with equation (2) obtaining
v2 = m22^(-1) * (v2' - m21*v1')
and then with equation (1) obtaining
v1 = m11^(-1) * (v1' - m12*v2)
Thus the decryption is unique. Note that in the above nothing
about M (in particular, whether it is singular or not) is assumed,
excepting that the diagonal elements of M have inverses.
M. K. Shen
------------------------------
From: Jeff Mullen <[EMAIL PROTECTED]>
Subject: computer program: extract consonants/vowels from input
Date: Fri, 07 Jul 2000 13:58:57 -0400
I am a computer programmer by trade. I am being asked
to write a computer program that, among other things,
must separaate the consonants and vowels in people's
names. It's an amusement--type in your name and date
of birth, and it will display tarot cards that are to
represent different aspects of you based on "letter
scores" derived from your name and on a function of
the year of your birth. Not necessarily an accurate
predicion, but, as I said, amusing sometimes.
To write the program, I need to write a submodule
that will distinguish the consonants and vowels in
a name. That's the tricky part.
I am posting to this list because there may be
encryption techniques that rely, at least in part,
on being able to either extract consonants and
vowels directly with some accuracy or--half of my
battle--can break a word (or, in the case of my
application, a proper name) into syllables.
There are arguments that "w" is a vowel when used
in words like "own" and "skew," but a consonant in
words like "Winter" (there is an argument that "w"
is a vowel in "Edward" but not in "Walter"). There
is an argument that "y" is a vowel in "sky" but
not in "Yellow" (there is an argument that "y" is
a vowel in "Jeffrey" :) :) :) but not in "Yosemmitie").
So...I'll admit that I'm no expert on the subject. Can
somebody help me with a set of rules for determining
whether "w" and "y" (and maybe even "h" or a few others)
is a consonant or a vowel, based on its context within
a proper name? If you can, I'll release the part of the
program that can determine whether a letter is a
consonant or a vowel into the public domain so that
everyone can use it.
Part of the problem, at least as far as I've been
able to define it, is the context of a vowel not
within a word but within a syllable. If there's
some reliable way for a computer to correctly break
a word (proper name) into syllables, then using
it will make it easier to determine whether a
letter in that syllable is a consonant or a vowel.
So...if anybody knows of any concepts or computer
programs (I'll gladly pay somebody else for his or
her work) that I could make use of in my own computer
program, please let me know.
Thanks in advance.
Jeff Mullen
Lead Programmer
Cleveland Productions, Inc.
------------------------------
From: Quisquater <[EMAIL PROTECTED]>
Subject: Re: Prime Numbers?
Date: Fri, 07 Jul 2000 20:06:58 +0200
Florian Weimer wrote:
>
> Quisquater <[EMAIL PROTECTED]> writes:
>
> > > I think the proof is correct, for the following reason: First, show
> > > that a number is prime if and only if it is not divisible by other
> > > primes. Under the assumption that n is the largest prime, n! + 1 is
> > > prime, because no prime numbers (which are in the range 1 .. n) divide
> > > it. But n! + 1 is larger than n, contradiction.
> >
> > No! It is only a proof that it is a product of primes greater than n.
>
> Strictly speaking, this is not true. The proof outlined above only
> proves that the number of prime elements in Z is not finite. The
> problem seems to be that most reasoning is done on the base of a false
> assumption, and people tend to think that the consequences of a false
> assumption are true if they can be proved using the assumption.
Sorry. I read incompletely. I was following 2 threads in parallel about the
same subject and the other one is wrong. By the way I also prefer the
"constructive" version of the proof (give me all the prime numbers you know
and I'll give you a new one).
========
Universit� de Louvain
UCL Crypto Group
see http://www.dice.ucl.ac.be/crypto
t�l. 32.10.47.25.41 (connected to my voicebox and cellular phone)
fax: 32.2.358.55.83 (only for me)
SMS: send an email (only the subject will be transmitted) to
[EMAIL PROTECTED]
------------------------------
** 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
******************************
