Cryptography-Digest Digest #729, Volume #13 Wed, 21 Feb 01 12:13:01 EST
Contents:
Re: New unbreakable code from Rabin? ([EMAIL PROTECTED])
Re: New unbreakable code from Rabin? ([EMAIL PROTECTED])
Re: New unbreakable code from Rabin? (Mok-Kong Shen)
Re: New unbreakable code from Rabin? (Mok-Kong Shen)
Re: The Key Vanishes: Scientist Outlines Unbreakable Code, Read it and Weep Boys
("*")
___indeed 2x2 Matrix RSA (kctang)
Re: ___indeed 2x2 Matrix RSA ("Jakob Jonsson")
Re: Is there an algorithm to sequentially enumerate all transcendental (Dave Seaman)
Re: The Key Vanishes: Scientist Outlines Unbreakable Code, Read it and (Nemo psj)
Re: 448 bits Hash algorithm (John Myre)
Re: "RSA vs. One-time-pad" or "the perfect enryption" (John Myre)
Re: New unbreakable code from Rabin? (David A Molnar)
Re: New unbreakable code from Rabin? (John Myre)
Re: CipherText patent still pending (William Hugh Murray)
[ANNOUNCEMENT] cdcProvider (java cryptography) (KryptoProvider-Administrator)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: New unbreakable code from Rabin?
Date: 21 Feb 2001 06:04:47 -0500
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] wrote:
>
>> All one requires is that the weak encryption used to indicate
>> how to extract a key from the public pool, be strong enough
>> to resist an interceptor's efforts at decryption for a week
>> (long enough until the pool has "auto-erased").
> Couldn't an eavesdropper monitor the communications and
> record simultaneously (during the time the communication
> partners negotiate) the bits in the public pool for
> later use?
One has to be a bit cleverer in the implementation, of course.
Avoid traffic analysis (not so much for when messages are transmitted
but for what parts of the public pool are extracted and WHEN).
For example, provided that at most one week's data can be stored
and one has an encryption method that resists encryption for two weeks.
Week one: On monday send information on data to be extracted this
week.
Use those as the key for the next week.
(this is why I wanted the encyprtion to resist attacks for two weeks-
if it only resisted attacks for one week, the next monday you would
have decrypted it and if you could store one week's data, you would
be able to store the data and still have it when you decrypted
the information on what data to extract for the "session keys")
If one can predict when messages are transmitted and know that
at that time the bits from the public pool are extracted for
the session key (or just predict what bits from the random pool
will be used) then one doesn't have to store all the bits
from the too voluminous pool (and can reduce the storage or use
the simultaneous bits).
One does have to avoid letting an interceptor obtain information
on what bits of the random pool are used until he manages to
decrypt any message sent which indicates the bits used
(by which time it will be too late for him) so there are things
one has to watch out for...
But one can boot strap weak encryption to secure key sharing depending
on the size of a random data pool, amount of storage available,
security of the weak encryption (if it can resist attacks for
a month and the pool is large ...), etc.
I'm sure there are many more details than the NY Times mentioned ...
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: New unbreakable code from Rabin?
Date: 21 Feb 2001 06:12:23 -0500
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] wrote:
>>
> [snip]
>> Black body (universal background) radiation from any
>> location at any time. Minute by minute stock fluctuations.
>> The density of the cloud cover on Jupiter. Possibly a service
>> that provides such a stream (from a satellite, I saw mentioned
>> in the article ... but I would not trust such a service provider
>> who could use a pseudo-random generator and so he would be
>> able to reconstruct any portion of the data stream at any
>> later time - it would not be "auto-erasing," transient, but
>> knowledge of the generator for the pseudo-random number
>> generator would enable one to "unerase" it).
> You seem to point to a problem. If there is no central
> service, how could it be ensured that everyone access the
> same stream and not eventually manipulated (and also
> differing) copies? If there is a central service, the
> issue of trust arises.
Yes ... one needs a transient, public, random pool.
Of course, if you are the US and want to set up such for your
armed forces (broadcast by satellite, for example) you'll
probably take care to do it right.
If you are the NSA setting it up for the public to use,
I would guess that you would use a pseudo-random number
generator for the public pool so you (at the NSA) can
"unerase" transient data and decrypt messages.
Of course, if you and your recipient have radio telescopes to
extract data from the universal background radiation at specific
right ascension, declination, time (and then transform it:
using the known distribution of entrop in black body radiation
extract n bits of randomness for an n bit key) you're in better
shape.
Or, you can just forget it if you can securely transmit a one
time pad (do that, use it and then erase it). But that would
require you to be able to *securely* transfer a pad (OK if you
are the US and can send the fleet to bring a copy to an
embassy, I guess) - it would be nicer to be able to use weaker
encryption and bootstrap to secure keys anyway.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: New unbreakable code from Rabin?
Date: Wed, 21 Feb 2001 12:36:29 +0100
Sundial Services wrote:
>
> Actually, some of the now-declassified crypto systems used by NATO in
> the 1950's relied upon a continuous stream of data, and steganography
> within that stream to conceal whether a message was passing through or
> not. Details of what the non-message stream consisted of were not
> disclosed. {Refer to the "Nautical Brass" websites for info about this
> system.}
>
> It seemed to me from reading the description that this system would
> trade high security for relatively small bandwidth. I don't know how
> many channels could be monitored simultaneously. Good enough for a ship
> at sea, which is what Nautical Brass was talking about, but I have no
> idea how the signals originated. Perhaps they were of a one-to-many
> nature, e.g. "nuclear war has been decQ%@!#%@..." ;-)
I also conjecture that scheme could be equivalent to one
using a PRNG to decide whether to send an information bit
(preferably encrypted) or to send random dummy bits. By
increasing the proportion of dummy bits, one could eventually
exceed the capability of the opponent to store the whole
stream for later examination. (BTW, I implemented such a
probabilistic scheme.)
M. K. Shen
===============================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: New unbreakable code from Rabin?
Date: Wed, 21 Feb 2001 12:41:11 +0100
[EMAIL PROTECTED] wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
> > Couldn't an eavesdropper monitor the communications and
> > record simultaneously (during the time the communication
> > partners negotiate) the bits in the public pool for
> > later use?
>
> One has to be a bit cleverer in the implementation, of course.
>
> Avoid traffic analysis (not so much for when messages are transmitted
> but for what parts of the public pool are extracted and WHEN).
>
> For example, provided that at most one week's data can be stored
> and one has an encryption method that resists encryption for two weeks.
>
> Week one: On monday send information on data to be extracted this
> week.
> Use those as the key for the next week.
>
> (this is why I wanted the encyprtion to resist attacks for two weeks-
> if it only resisted attacks for one week, the next monday you would
> have decrypted it and if you could store one week's data, you would
> be able to store the data and still have it when you decrypted
> the information on what data to extract for the "session keys")
>
> If one can predict when messages are transmitted and know that
> at that time the bits from the public pool are extracted for
> the session key (or just predict what bits from the random pool
> will be used) then one doesn't have to store all the bits
> from the too voluminous pool (and can reduce the storage or use
> the simultaneous bits).
>
> One does have to avoid letting an interceptor obtain information
> on what bits of the random pool are used until he manages to
> decrypt any message sent which indicates the bits used
> (by which time it will be too late for him) so there are things
> one has to watch out for...
>
> But one can boot strap weak encryption to secure key sharing depending
> on the size of a random data pool, amount of storage available,
> security of the weak encryption (if it can resist attacks for
> a month and the pool is large ...), etc.
>
> I'm sure there are many more details than the NY Times mentioned ...
I have the impression that the scheme is in some (at least
more or less remote) sense not different from the busy
channel where one sends lots of rubbish during the time
without proper messages.
M. K. Shen
------------------------------
From: "*" <[EMAIL PROTECTED]>
Subject: Re: The Key Vanishes: Scientist Outlines Unbreakable Code, Read it and Weep
Boys
Date: Wed, 21 Feb 2001 13:43:11 +0100
Just know some people don't have web access, only newsgroup...
Douglas A. Gwyn wrote in message <[EMAIL PROTECTED]>...
>"." wrote:
>> From the article at:
>> http://www.nytimes.com/2001/02/20/science/20CODE.html?pagewanted=all
>
>Why are you posting copyrighted material when we already had the
>URL for it? Very uncool.
------------------------------
From: kctang <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: ___indeed 2x2 Matrix RSA
Date: Wed, 21 Feb 2001 16:11:58 +0800
Dear Forum,
Due to accident, I invented an encryption/decryption scheme that
seemed to "work" and of which I knew the weakness. But please try to
provide a convincing crack.
It was based on ideas of RSA, like this:
Key preparation:
================
Choose primes p and q. Compute n = p*q.
Choose a random e relatively prime to 2(p-1)(q-1).
Compute d such that e*d = 1 mod 2(p-1)(q-1).
e stands for encrypt, d stands for decrypt.
Public key is (n,e). Secret key is d.
Encrypt 3 components at a single run
====================================
Suppose A,B,C are positive integers less than n.
Let M =
[A B ]
[C -A ]
M is encrypted to M^e taking mod n element-wisely.
We can use the standard binary method for MATRIX
exponentiation mod n, for "fast" computation.
Decrypt 3 components at a single run
====================================
( M^e )^d taking mod n element-wisely.
We can once again use the standard binary method for MATRIX
exponentiation mod n.
Why it works?
=============
(M^e)^d is M again. Most of the time it works!
Question:
=========
1) Can you explain why this method works? (Anyhow, I shall
provide an example tomorrow.)
2) Please provide a convincing crack, not just simply mention its
weakness.
------------------------------
From: "Jakob Jonsson" <[EMAIL PROTECTED]>
Subject: Re: ___indeed 2x2 Matrix RSA
Date: Wed, 21 Feb 2001 16:35:48 +0100
> Why it works?
> -------------
> (M^e)^d is M again. Most of the time it works!
In fact, it works as soon as det M != 0 mod n.
> Question:
> ---------
> 1) Can you explain why this method works? (Anyhow, I shall
> provide an example tomorrow.)
Since the square of M is equal to diag(a^2+bc, a^2+bc), the procedure will
work as soon as ed-1 is a multiple of 2*lcm(p-1, q-1) (e.g., (p-1)(q-1)) and
a^2+bc != 0 mod n.
> 2) Please provide a convincing crack, not just simply mention its
> weakness.
This is not a crack, but an observation:
M^e = [e = 2k+1] = M^2k * M = (a^2+bc)^k * M
Hence b*a^{-1} mod n, c*a^{-1} mod n, and b*c^{-1} mod n are easy to extract
from M^e. This means that knowing one of the values a, b, c is enough to
break the scheme. On the other hand, if b and c are completely random and
independent, the task will be to determine a from a^e, b/a, and c/a, which
is no easier than determining a from a^e, i.e., computing eth roots modulo
n. In either case, nothing is gained compared to ordinary RSA.
Jakob
------------------------------
From: [EMAIL PROTECTED] (Dave Seaman)
Crossposted-To: sci.math
Subject: Re: Is there an algorithm to sequentially enumerate all transcendental
Date: 21 Feb 2001 10:33:12 -0500
In article <[EMAIL PROTECTED]>,
Trevor L. Jackson, III <[EMAIL PROTECTED]> wrote:
>Virgil wrote:
>> In article <[EMAIL PROTECTED]>, jtnews
>> <[EMAIL PROTECTED]> wrote:
>> > Jan Kristian Haugland wrote:
>> > > jtnews wrote:
>> > > > Is there an algorithm to sequentially enumerate
>> > > > all possible transcendental numbers?
>> > Thanks for the quick response!
>> > Is there some reference anyone can give
>> > where I can find mathematical proof of this?
>> The first proofs of the uncountability of the reals are due to Georg
>> Cantor.
>Are there any non-diagonalization proofs?
There are at least two, but both involve things that are more
high-powered than diagonalization.
One is the measure-theoretic proof. The Lebesgue measure of the interval
[0,1] is 1. Every countable set has measure 0. Therefore, [0,1] must be
uncountable.
Another comes from the Baire Category Theorem: a complete metric space
is not the union of a countable collection of nowhere dense sets. The
reals are a complete metric space, and each single-point set is nowhere
dense in the reals. Therefore, the reals are uncountable.
--
Dave Seaman [EMAIL PROTECTED]
Amnesty International calls for new trial for Mumia Abu-Jamal
<http://www.amnestyusa.org/abolish/reports/mumia/>
------------------------------
From: [EMAIL PROTECTED] (Nemo psj)
Date: 21 Feb 2001 15:49:55 GMT
Subject: Re: The Key Vanishes: Scientist Outlines Unbreakable Code, Read it and
Oh so what... Are you going to call his momy? People need to learn to relax.
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: 448 bits Hash algorithm
Date: Wed, 21 Feb 2001 09:00:09 -0700
Has anyone considered how many bits one could safely
get out of Panama? I know it's designed for 256 bits,
but since it also functions as a PRNG, it would be
trivial to "pull" again for 512 bits (costing at most
3% more time).
JM
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: "RSA vs. One-time-pad" or "the perfect enryption"
Date: Wed, 21 Feb 2001 09:14:28 -0700
Joseph Ashwood wrote:
<snip>
> What you are searching for is purely unbreakable cryptography, even OTP does
> not qualify (you can given very large quantities of time generate each
> possible decryption) under your rules.
<snip>
Huh? Do you mean this? If so, could you please explain?
JM
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: New unbreakable code from Rabin?
Date: 21 Feb 2001 16:13:49 GMT
[EMAIL PROTECTED] wrote:
> Perhaps the Rabin result improves on these figures, or uses a
> different security model. It is curious that it is getting so much
The security model is essentially the same. More details are available at the
Aumann and Rabin CRYPTO '99 paper:
http://link.springer.de/link/service/series/0558/bibs/1666/16660065.htm
This paper is a bit out of date now, but the basic ideas are all there. I think
that updated work has been submitted and (insh'allah) may appear in the usual
places later this year.
> attention when previous results are known for what seems to be a
> similar problem. Perhaps the newspaper story misrepresents the novel
> aspect of the results.
I'm not sure why the New York Times does what it does. For what it's worth, the
Aumann-Ding-Rabin scheme is more computationally efficient (requiring only XORs,
no hashes, no humongous finite field computations) and acheives a better
security bound than previous schemes. There is some discussion of this in the
"previous work" section of the paper referenced above.
-David
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: New unbreakable code from Rabin?
Date: Wed, 21 Feb 2001 09:29:29 -0700
Ichinin wrote:
<snip>
> Dare i mention the syncronisation problem for both parties;
> i.e. do they need precicely tuned atom clocks?
<snip>
Not necessarily. If there is one publicly available stream
of bits, there can be another one, broadcast simultaneously
and synchronously, that acts as a timing channel. (I.e., the
second channel is not random data.)
JM
------------------------------
From: William Hugh Murray <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: CipherText patent still pending
Date: Wed, 21 Feb 2001 16:40:29 GMT
Mok-Kong Shen wrote:
> Bryan Olson wrote:
> >
> > Mok-Kong Shen wrote:
> > > Bryan Olson wrote:
> > > > Hard to believe you are looking at the same world as am I.
> > > > There's a huge need, and call, for crypto research. But a new
> > > > symmetric cipher not known to be secure or insecure just makes
> > > > a large pile bigger.
> > >
> > [...]
> > > But don't you
> > > see that at schools the pupils are continuing to write
> > > compositions (after you have left school)? Should they
> > > stop writing??
> >
> > Experts teaching writing say to write every day. I've never
> > heard an expert cryptologist recommend cipher design as an
> > exercise.
>
> So any pupil of crypto never gets to do an exercise of a
> design and hence will also have zero chance of making
> a good (or even half-good) one in his life and, as a
> consequence, all good ciphers that exist today ultimately
> die out (being no longer secure enough for the future
> computing power and techniques) after the current
> generation of crypto experts die out. Indeed an extremely
> fine and highly desirable scenario for certain government
> people (cf. export regulations, Wassenaar Arrangements,
> RIPA, etc.).
>
> > > It may be noted that there is a parallel
> > > (monitored) group sci.crypt.research which is supposed to
> > > be a forum for research stuffs. Since you apparently
> > > pose a rather high standard on materials you read, I warmly
> > > recommend you to switch to that group,
> >
> > There's a myth that sci.crypt is for the less technical
> > material. Check the charter; you may be in the wrong place.
>
> I don't think that I am in the wrong place. True, there are
> sometimes also matters related to politics etc. in the group
> and occassionally I post follow-ups in such threads, but
> that's tolerated to some extent, if I don't err. For the
> rest of what I have posted so far, I am quite certain that
> my materials are technical. Whether they are of high or low
> level and whether they are correct or erroneous can of
> course be questioned and, in fact, the very purpose of my
> posting is to learn something from the benevolent experts
> but that has nothing to do with 'technicality' of the
> materials per se. (I believe that I have, as a 'pupil',
> occassionally even succeeded to help my co-'pupils' a tiny
> little bit through what I happen to have learned, but that's
> another issue.)
>
> My point has been that sci.crypt is open to all beginners
> and that persons who desire to 'only' read higher quality
> stuffs are better advised to subscribe to sci.crypt.research
> instead, while experts (who by definition have barely
> anything to learn anywhere anytime) having time, interest
> and patience to kindly help the beginners should continue
> to remain in this group, which will naturally in large part
> consist of 'learners' (not 'learned') and non-technical
> stuffs should largely be posted only to other appropriate
> internet groups, e.g. talk.politics.crypto. (I haven't
> been very long in this group. But I believe that one can
> live with the current amount of non-crpto stuffs and
> I have the impression that the situation is better than
> years before.)
>
> BTW, I suppose that even experts who get annoyed about
> chaffs could well live with our group. At least with the
> type of newsreader I use there is sufficient possibility
> to select (screen) stuffs that one wants to read, since
> one can sort according to subjects and senders. Most subject
> lines provide ample hints of whether the threads could
> eventually be interesting and with time one could, if
> desired, build up private lists of posters whose stuffs
> one likes or doesn't like to read (a positive and a negative
> list) in ways analogous to one's selection of media (films,
> TV-shows, songs, books, etc.) according to the names of
> the actors involved. I heard that there is even software for
> automatically screening away posts from undesirable sources
> (sort of personal firewall, I guess), but I don't know any
> details about that.
>
> M. K. Shen
> --------------------------
> http://home.t-online.de/home/mok-kong.shen
Perhaps it would be useful to distinguish between pupil and student,
amateur and apprentice. Many of the examples that we see here are by
the cryptographic equivalent of a hacker. That is to say they ar by
those trying to learn cryptography by experimentation. They are trying
to do it without benefit of a master or a mentor. They are trying to do
it without benefit of studying the literature. They are trying to do it
without first mastering the necessary prerequisite mathematics. They
are trying to do it without studying the classical worked examples.
Cryptography is a very difficult discipline to learn in this manner. I
suppose that it is possible. A few hackers do manage to evolve into
master programmers but it is rare. When one is trying to learn to
program by experimentaion, one at least enjoys the benefit of prompt
feedback. One can begin with a closed set of primitives. One also
enjoys the benefit of sample code that can be understood with a minimum
of preparation. The amateur crypographer enjoys few of these benefits.
It is not a field that is easy to enter at the end.
------------------------------
From: KryptoProvider-Administrator <[EMAIL PROTECTED]>
Crossposted-To: comp.lang.java.security
Subject: [ANNOUNCEMENT] cdcProvider (java cryptography)
Date: 21 Feb 2001 16:52:27 GMT
R E L E A S E A N N O U N C E M E N T
======================================
The cdcProvider group of the Technical University of Darmstadt, Germany
would like to announce the first publicly available release of cdcProvider,
a powerful toolkit for the Java Cryptography Architecture.
The cdcProvider packages support a wide range of cryptographic primitives
(i.e. IFP, DLP and ECDLP-based asymmetric algorithms) and will allow you to
create flexible cryptographic applications in a rapid and timely manner.
The architecture of the cdcProvider is organized in a modular manner which
makes both parts of it easily exchangeable as well as the the whole
interoperable with other cryptographic providers.
The current release (version 1.9) implements the following features:
* Symmetric algorithms: DES, E2, IDEA, Mars, RC2/5/6, Rijndael (AES candidate),
SAFER+, Serpent, Twofish
* Message digests: MD4/5, RIPEMD160, SHA1
* Message authentication codes: HMAC-MD5, HMAC-SHA1
* Assymetric algorithms: ECDSA, ECElgamal, ElGamal, RSA
* Signature Schemes: DSA, RSA, ECDSA, RSA
In the near future we also plan to support ECAES, ECDH, ECES, ECNR and
algorithms based on computational problems in (quadratic) number fields.
For further information please see the official homepage of the
cdcProvider located at:
http://www.informatik.tu-darmstadt.de/TI/Forschung/cdcProvider
------------------------------
** 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
******************************
