Cryptography-Digest Digest #282, Volume #9 Thu, 25 Mar 99 08:13:03 EST
Contents:
Re: Symmetric vs. public/private (Patrick Juola)
Re: Hard problems? (Doggmatic)
Re: The Magic Screw, Non-Secret Encryption, and the Latest WIRED ("Douglas A. Gwyn")
Crytpo Gurus - Please comment on this sceneario (sb5309)
Re: unicity, redundancy and help ("Douglas de la Torre")
Re: pRNG that is "predictable to the left"? ("Steve Myers")
Re: Hard problems? (Doggmatic)
Re: compare RSA and D-Hellman ("Sam Simpson")
Re: RSA Algorithm (Scott Fluhrer)
Re: Decorrelated Fast Cipher (plus other block ciphers) (Daniele Finocchiaro)
PKI on LINUX ([EMAIL PROTECTED])
Re: Another TEA question (Mark Carroll)
Message Digest (Mark Carroll)
GOOD PRIME GENERATOR (GPG) (Mike L. Griebel)
Re: Maurer's Universal Statistical Test C (was Re: idea for random numbers (Mok-Kong
Shen)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: Symmetric vs. public/private
Date: 24 Mar 1999 14:38:57 -0500
In article <[EMAIL PROTECTED]>,
Bo Dömstedt <[EMAIL PROTECTED]> wrote:
>In a public key network, the Key Signing Authority first
>generates its own secret/public key pair. So do the network
>nodes. The public key, of a network node, must be signed
>by the Key Signing Authority, in order to be accepted as valid
>by the other nodes in the network.
>
>When transferring a public key, of a node, to the
>Key Signing Authority for signing, it is essential that
>a) It is possible, for Key Signing Authority, to prove
>that the key originates from the node in question,
>b) It is possible, for Key Signing Authority, to prove
>that the node is allowed to be a member of the network.
>
>The node may encrypt his public key by the public key
>of the Key Signing Authority... :
>It is then essential that
>a) The node can prove that the public key obtained,
>from the Key Signing Authority, is indeed the correct one.
>b) The Key Signing Authority can prove that the encrypted
>key originates from the node in question, and
>c) It is possible, for Key Signing Authority, to prove
>that the node is allowed to be a member of the network.
>
>Note that, in almost all literature (see 1 and 2!!), the above
>essential problems is ignored by a statement like "The key is
>first encrypted by the published /signing/ key" -- the key word
>here is "published". Do such things exist?
Of course they do. Read the PGP documentation, for instance.
One of the first things the developers did was published
their keys as part of the documentation.
-kitten
------------------------------
From: Doggmatic <[EMAIL PROTECTED]>
Subject: Re: Hard problems?
Date: Thu, 25 Mar 1999 07:35:19 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> > I've seen NP-complete problems, but what's an analogy which describes
PSPACE,
> > PSPACE-complete, or EXPTIME problems? Assume I know little to nothing about
> > number theory, information theory or complexity theory, other than those
> > terms.
>
> The generic PSPACE-complete problem is satisfyability of quantified boolean
> formulae.
This one sounds interesting ... what is it? I thought the boolean
satisfyability problem was NP-complete.
> Other exemples are:
> - Given a directed graph with a starting point s, and the following game:
> Two players move a pebble along the edges in turns, starting from s.
> A player looses if she moves to a vertex already visited or cannot move.
> Who wins the game?
> - Who wins a given game of Go (japanese game). The size of the board and
> the pebbles already present are variable in this problem.
>
___/Mike ...two legs good, four legs bad? ... Why conform?
__/. |
\-__ \___
\
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: The Magic Screw, Non-Secret Encryption, and the Latest WIRED
Date: Sat, 20 Mar 1999 03:46:01 GMT
John Savard wrote:
> The use of KEA with FORTEZZA at least appears to indicate that the NSA now
> trusts public key methods - with *unclassified*, but sensitive,
> information. The costs of traditional key distribution probably are not
> prohibitive for the protection of all (or some) classified material.
Actually, the STU-III secure phone system has for many years used
a nice scheme whereby the users have "crypto ignition keys" where
the private key is embedded in an on-CIK chip, multiple levels of
access are distinguished (the highest one is displayed on the
remote unit), and a Key Management Center is used to disown
compromised CIKs. Unfortunately the details of the algorithms
don't seem to have yet been openly published.
------------------------------
From: sb5309 <[EMAIL PROTECTED]>
Subject: Crytpo Gurus - Please comment on this sceneario
Date: Thu, 25 Mar 1999 15:50:39 +0800
I write this so as to learn something from your responses; if it is old
story, please don't flame me; I am a novice.
(I sent this two days earlier, but I did not see it in the group; so I
try again)
Consider this scenario :
Two persons are engaged to type, using computer keyboards, to produce a
series of numbers from 0 to 255. They are told that they should make
them random. These two series are later joined together to form a long
series.
My comment
==========
I don't really think that these two series will be random. Chance is
each series has its own bias, ie. biasness in one series is different
from the other.
Can this be used in OTP ? My initial feeling is YES. As described by
David Kahn in "Codebreakers" (I quote this from the book "Decrypted
Secrets - Methods & Maxim in Cryptography" by F. L. Bauer), that the
Baudot code prepared by typists in WWII contained biases. For example, a
typist would typically place its left-hand small finger at 1 and the
thumb at 5, and the right-hand small finger at 6 and the thumb at 0. The
numbers so produced indicate that the digits from 1 to 5 would normally
form a number; so was 6 to 0. In other words, numbers like 10293, 28375
which required typing with fingers from each hand were not often
created. Numbers with triple and more similar digits were very rare.
Yet, as noted by David Kahn, the numbers did not have enough pattern for
crypto-attack.
Your Comment
============
???
------------------------------
From: "Douglas de la Torre" <[EMAIL PROTECTED]>
Subject: Re: unicity, redundancy and help
Date: Wed, 24 Mar 1999 23:13:25 -0800
See the article "Unicity, DES Unicity, Open-Keys, Unknown-Keys" at
http://www.mcg.org.br/unicity.htm
------------------------------
From: [EMAIL PROTECTED] ("Steve Myers")
Subject: Re: pRNG that is "predictable to the left"?
Date: 20 Mar 99 03:23:03 GMT
Scott Fluhrer wrote in message <7cuog9$[EMAIL PROTECTED]>...
>In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] ("Steve Myers") wrote:
>
>>
>>It is an easy theorem to prove that a generator is unpredictable to the
left
>>iff the generator is unpredictable to the right iff the generator is
>>pseudo-random. Therefore, you have a generator which is predictable in
both
>>directions, you're just no aware of the predictibility in one direction.
As
>>a direct corollary your construction must fail, and so must all further
>>attempts.
>Either you are using an odd definition of unpredictable, or this statement
is
>false (or, there are no one-way functions).
>
>As a counterexample, consider the generator:
>
> X(n+1) = SHA( X(n) )
>
>where "SHA" is a one-way function (not necessarily the Secure Hash
Algorithm).
>
>Now, this generator is predictable to the right (one way functions are easy
>to perform, by definition), but unpredictable to the left (one way
functions
>are hard to invert, by definition).
This is not hard to predict because secure hashing gives you nothing about
unpredictability, if I take any
SHA and produce SHA' s.t. SHA'(x)= 00000||SHA(x), where || is the
concatenation operator, then SHA' remains secure as a
hash function, where presumably you have some strong collision resistance
property that SHA needs to satisfy in order to be secure.
Now, if you see a string 0000 from the left, then predict the next bit is
0, and you will be correct with a pretty high probability (I'm assuming that
SHA already does not produce a lot of strings of the form 0000 for random x,
which could be formalized, but I won't take the time).
>BTW: what's the proof of the easy theorem? Also, what definition of
>"pseudo-random" are you using in your statement?
Defn of pseudo-random (extreme intuition, poor formalism) there exists no
(non-uniform) infinite family {C_n} of poly sized circuits, which can
distinguish between a random input, and the result of a pseudo-random
generator on a random seed with probability >= \frac{1}{n^c} for all
constants c, and sufficiently large n.
Proof Sketch (Presumably the only semi-interesting Direction)
G is not pseudo-random=> G is not predictable from the left.
We use a hybrid distribution argument.
Let {D_n} be a distinguisher for G. Let p be the probability that D accepts
a pseudo-random string resulting from a random key, and let r be the prob
that D accepts a random string. By assumption |p-r|> \frac{1}{n^c} for some
constant c, WLOG assume that p>=r .
Let r_1,...r_n be completely random bits, let p_1,...,p_n be pseudo-random
bits.
Take a circuit D_n of input size n. Let q_i be the probability that D_n
accepts on input of p_1,...,p_i,r_{i+1},...,r_n.
Clearly q_n=p and q_0 =r. So q_n - p =0 and q_n -r = \frac{1}{n^c}.
Let j be the smallest number s.t. q_j - r >= \frac{1}{n^{c+1}}. (Its easy
to see that such a j is gauranteed to exist).
Now we construct a circuit family {C_n} which predicts the bit j.
Let C_n be a circuit which takes j-1 bits as input I_1,...,I_{j-1}. It runs
the circuit D_n on input (I_1,...,I_{j-1},R_j,....,R_n) where the R_i's are
random bits. If D_n accepts then C_n predicts the j^th bit to be R_j,
otherwise it outputs 1-R_j.
A quick probabilistic calc will show that the probability of being correct
is better than \frac{1}{n^{c+2}}, and we're done.
And we can later fix all random bits, to get a completely deterministic
circuit using the usual tools, if it is so desired.
Hope you're convinced.
Steve
P.S> An easy theorem does not translate into an easy to post to a newsgroup
theorem.
P.S.S> I think Yao was responsible for this result originally, but I could
be wrong.
>
>--
>poncho
>
>
------------------------------
From: Doggmatic <[EMAIL PROTECTED]>
Subject: Re: Hard problems?
Date: Thu, 25 Mar 1999 07:37:48 GMT
In article <7cofoi$gl3$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> In article <7cne1o$li5$[EMAIL PROTECTED]>,
> Doggmatic <[EMAIL PROTECTED]> wrote:
> > In article <7cj2lf$j0m$[EMAIL PROTECTED]>,
> > [EMAIL PROTECTED] (Patrick Juola) wrote:
> > > In article <7cfhoi$ti4$[EMAIL PROTECTED]>,
> > > Doggmatic <[EMAIL PROTECTED]> wrote:
> > > >I've seen NP-complete problems, but what's an analogy which describes
> PSPACE,
> > > >PSPACE-complete, or EXPTIME problems?
> >
> > Hmmm ... my original question is poorly worded. I'm looking for an actual
> > example of a problem of one of those types.
>
> The equivalence problem for semi-extended regular expressions requires
> both exponential time and space.
>
> See:
>
> Aho, Hopcroft & Ullman
> The Design and Analysis of Computer Algorithms
> Chapters 10,11,12
The book doesn't exist online anywhere, and it appears to be kinda old. I
could order it from a bookseller, but is there anyone willing to explain the
"problem for semi-extended regular expressions?"
Thanks.
>
> -----------== Posted via Deja News, The Discussion Network ==----------
> http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
>
___/Mike ...two legs good, four legs bad? ... Why conform?
__/. |
\-__ \___
\
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: "Sam Simpson" <[EMAIL PROTECTED]>
Subject: Re: compare RSA and D-Hellman
Date: Thu, 25 Mar 1999 09:33:09 -0000
Don,
Have you got a pointer to further information on this?
Regards,
--
Sam Simpson
Comms Analyst
http://www.scramdisk.clara.net/ for ScramDisk hard-drive encryption &
Delphi Crypto Components. PGP Keys available at the same site.
If you're wondering why I don't reply to Sternlight, it's because
he's kill filed. See http://www.openpgp.net/FUD for why!
DJohn37050 wrote in message
<[EMAIL PROTECTED]>...
>BTW, Dan Boneh has recently proved that attacking ECDH is fully
exponential if
>ECDLP is. This analogous statements are not (known to be) true for
DH and DLP
>and RSA and IFP.
>Don Johnson
------------------------------
From: Scott Fluhrer <[EMAIL PROTECTED]>
Subject: Re: RSA Algorithm
Date: Thu, 25 Mar 1999 10:05:51 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (STL137) wrote:
>Hello.
>Is there anything wrong with this algorithm I'm using to generate moderately
>(actually, darn weak) RSA keys, and then use them to encrypt and decrypt
>information?
>
>Pick a random prime P.
>Pick a random prime Q. (Of course P can't equal Q)
>Set N = P*Q.
>Find (P-1)(Q-1) and some number R so that gcd(R, (P-1)(Q-1) ) = 1.
>Compute S so that R * S = 1 mod (P-1)(Q-1).
>Do the last two steps for ten additional R values, and choose the R,S pair that
>has the smallest S. <== I do this so decryption doesn't take a very long time.
>I don't *think* this is a bad thing to do...
Well, checking only eleven pairs, and picking one isn't going to be much worse
than picking one pair at random. However, extremely low private exponents are
known to be weak, so you probably don't want to do this with a billion pairs.
(Also, if you are looking at minimizing decryption time, why don't you take the
S that require the least number of multiplies, rather than the strictly smallest
one)
>R, S becomes the public and secret keys, with N as the public modulus.
>The keysizes can't realistically go much above the strength of a 250-digit
>composite number, so I'm not caring about "strong primes".
>
>To encode information, I take english text and transform it into numbers (ASCII
>codes). I then break it up into number chunks < N, and perform encryption on
>each separate chunk. To decrypt, I perform decryption on each separate chunk,
>reintegrate it into one long string of ASCII codes, and make it English text
>again. I l also accounted for the fact that ASCII codes often start with 0 (I
>affix a random number between 1 and 9 inclusive before every chunk, which is
>stripped off after decryption).
Bad idea, for several reasons:
- Two identical passages have a 10% probability of being encrypted the same
way. This can easily happen if you are encoding boilerplate text, or one
message quotes the other. This leaks a lot of information about the
plaintext. For example, if the attacker has the plaintext to one of the
messages, he then has part of the plaintext to the other. At the very
least, the attacker will realize that the two messages are related.
- It makes it easy for an attacker to verify whether a particular plaintext
corresponds to a particular ciphertext -- all he needs to do is encrypt
the plaintext with the 9 possible random numbers before every chunk.
- This is a lot slower than it needs to be (more than 100x slower on long
messages). Typically, what people do in this situation is pick a 'session
key', encrypt the session key using RSA, and send that, along with the
plaintext encrypted using a symmetric cipher (eg. DES or blowfish) using
the session key. Unless your message is only one or two chunks, the
greater speed of the symmetric cipher more than makes up for the
additional complexity.
--
poncho
------------------------------
From: Daniele Finocchiaro <[EMAIL PROTECTED]>
Subject: Re: Decorrelated Fast Cipher (plus other block ciphers)
Date: Thu, 25 Mar 1999 13:07:43 +0000
[EMAIL PROTECTED] wrote:
>
> Does anybody know anything about DFC? Just wondering if it's any good.
DFC is one of the candidates in the AES competition, created by Serge Vaudenay
and a group of French people (mainly from Ecole Normale Superiure, Paris).
You can find complete information at http://www.dmi.ens.fr/~vaudenay/dfc.html
>From what I know of it, its main characteristics are:
- decorrelation theory gives mathematical proof of resistance against some known
attacks. DFC was built around this theory, such that a slight variant of it
(where a certain function is supposed to be random) is provably secure against
those particular attacks.
- it is designed mainly for 64bit platforms, where its performance is very good.
However, it fits also in smaller processors and smart cards (but it becomes
quite slow in comparison to other algorithms).
- so far, only minor weaknesses in the key schedule have been found, and they
have been addressed in a "DFC Update" proposal at AES2 conference.
Ciao,
* Daniele Finocchiaro
------------------------------
From: [EMAIL PROTECTED]
Subject: PKI on LINUX
Date: Thu, 25 Mar 1999 10:48:03 GMT
Hi everybody,
I would like to know whether there is Public Key Infrastructure related
toolkit available for LINUX like the Microsoft Crypto API available on
Windows platforms. I would also like to know whether they are available
whether they are available for free.
I looked up the sites www.kernel.org and www.linux.org, but they do not have
any information on this.
Any help on this would be appreciated.
Regards
Shantanu
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (Mark Carroll)
Subject: Re: Another TEA question
Date: 25 Mar 1999 12:31:44 +0000 (GMT)
In article <[EMAIL PROTECTED]>,
Stephen C. Gilardi <[EMAIL PROTECTED]> wrote:
><[EMAIL PROTECTED]> wrote:
>
>> Does anybody know where I can find info on TEA-x (extended TEA)? I would
>> really like to know.
(snip)
><http://www.cl.cam.ac.uk/ftp/users/djw3/xtea.ps>
>
>If "extended TEA" is something different, then perhaps someone else will
>chime in with its locaion.
At least, the document you kindly found for Tom describes what's
probably the most secure version of TEA, AFAIK.
-- Mark
------------------------------
From: [EMAIL PROTECTED] (Mark Carroll)
Subject: Message Digest
Date: 25 Mar 1999 12:01:52 +0000 (GMT)
In article <[EMAIL PROTECTED]>,
Jim Shapiro <[EMAIL PROTECTED]> wrote:
(snip)
>[EMAIL PROTECTED] wrote:
>
>> Question:
>>
>> Given a 256 bit message, and a 128 bit digest, are there 2^128 256 bit
>> messages that will make the same message digest?
(snip)
>Perhaps on average, but this depends on how the MAC distributes the
>messages among the digests.
>It is possible that all possible messages are converted to only 100
>different digests and all of the other digests go unused..
In case this causes any confusion:
Even if all possible messages are converted to only 100 different
digests, it is still true that there exist 2^128 256-bit messages that
will make the same 128-bit message digest. This statement always
holds, irrespective of how the MAC distributes the messages among the
digests.
You're answering a related question that Tom may have in fact meant to
ask.
(HTML posting snipped - please don't include these!)
-- Mark
------------------------------
From: Mike L. Griebel <[EMAIL PROTECTED]>
Subject: GOOD PRIME GENERATOR (GPG)
Date: Thu, 25 Mar 1999 12:26:09 GMT
Reply-To: [EMAIL PROTECTED]
Note: I posted this at sci.math yesterday. Today I found out that someone
named 'torres' has discovered this algorithm before me, last year --
actually, I suspect none of us came first then. I didn't know, so I had named
the algorithm independently.
(Also, there seems to have been much heated debate over this algorithm of
torres', both on sci.math and sci.crypt; apparently because people use the
same words for different things. I don't want to be part of that discussion;
this is probably a good algorithm if you want to calculate ALL the primes
with certain characteristics up to a limit, but if you want to find A FEW
primes in an interval, pick a number at random and test for primality. The
same goes for phase 2 below.)
=======================================================
Below my prime generator. Actually it's a prime candidate generator. It
generates PHI(G) candidates btw. 0 and G-1 in practically linear time,
if G = product of first n primes. There can't be any other candidates in
the interval examined.
Before ditching my algorithm completely, please take the time to try it
out. For instance, find all twin primes up to 2310 using only pen and
paper. It works quite well; you find 135 candidates in no time, and then
you have to check those manually, for instance using a table of primes
(yes, you have to cheat).
******************************************************
** G R I E B E L ' S "GOOD PRIME GENERATOR" (GPG) **
******************************************************
DEFINITIONS
-----------
pn = the n'th prime
G0 = 1
n
Gn = PROD pj = the product of the first n primes
j=1
PHASE 1 (Generate Candidates)
------------------------------
M0 = { 0 } (recursion base)
Mn* = { y | y = m + k*G(n-1),
m element of M(n-1),
k = 0,1,..,(pn - 1) }
Mn = { y in Mn* | ( y not congruent w. 0 (mod pn) ) }
PHASE 2 (Pruning)
------------------
Mn = { y in M(n-1) | ( y not congruent w. 0 (mod pn) ) }
Phase 2: substitute with your own favorite algorithm. You can find more
about my prime generator on:
http://www.geocities.com/Athens/8201/primes/
To find primes with a distance of 2, i.e. twin primes, modify the checks
in phase 1 and 2 to read "Both y & y+2 not congruent w. 0 (mod pn)".
Similarly for other kinds of tuples, for instance (p, p+210, p+420,
p+630, p+...., p+9*210) -- a stretch of 10 primes in arithmetic
progression, with a difference of 210 between consecutive pairs.
First occurrence of gaps: You could generate primes with a distance of
e.g. 1000, and then check the intermediate numbers for primality.
Consecutive primes in arithmetic progression: find primes in arithmetic
progression, and check the numbers in between for primality.
FACTS ABOUT MY ALGORITHM:
1. It is a variation of the Sieve of Eratosthenes,
2. It works on classes of numbers (modulo something).
3. You can calculate primes, twin primes, prime tuples
in a reasonable time, armed with only pen and paper.
4. It is very simple to implement the algorithm in some
programming language.
If you would like to publish this algorithm, please make
a reference to the URL mentioned above.
Have fun!
Sincerely,
Mike L. Griebel (iN*Tp) ... dreams, lexicography, Japanese, Danish, a.o.
___________________________________________________________
[EMAIL PROTECTED]; http://www.geocities.com/athens/8201/
GCS/@ d?(pu)>@ s-:+ a36 C++ W++ w--- O- M++ R* !tv b+++ G e+++ h+ r y+
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Maurer's Universal Statistical Test C (was Re: idea for random numbers
Date: Thu, 25 Mar 1999 13:05:34 +0100
You should state the confidence interval of the statistic instead
of the mean. The case L=6 can also be interesting, though a little
bit longer in program length.
M. K. Shen
------------------------------
** 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
******************************
