Cryptography-Digest Digest #158, Volume #9 Sun, 28 Feb 99 08:13:03 EST
Contents:
Re: Why Physical Randomness? (Terry Ritter)
Re: One-Time-Pad program for Win85/98 or DOS (Terry Ritter)
need simple symmetric algorithm ("Daniel Feurle")
Secure Elections? ([EMAIL PROTECTED])
Re: Miller-Rabin prime test. Random bit size (Bryan Olson)
Re: Unicity of English, was Re: New high-security 56-bit DES: Less-DES ("Douglas A.
Gwyn")
Re: Miller-Rabin prime test. Random bit size ("Michael Scott")
Re: New high-security 56-bit DES: Less-DES (Bryan Olson)
Re: ElGamal key generation (Wei Dai)
Re: Testing Algorithms [moving off-topic] (Paul Crowley)
Re: A New Public-Key Cryptosystem (Bryan Olson)
Re: True Randomness - DOES NOT EXIST!!! (BRAD KRANE)
Re: Testing Algorithms (Herman Rubin)
Re: Can the quantum computer determine the truth from a lie? ("Jay")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Why Physical Randomness?
Date: Sun, 28 Feb 1999 07:08:43 GMT
On 27 Feb 1999 14:45:46 -0500, in <7b9i1a$[EMAIL PROTECTED]>,
in sci.crypt [EMAIL PROTECTED] (Herman Rubin) wrote:
>[...]
>It depends on the purpose. For simulations, where there will not
>be a need to use the numbers again, and where independence is
>important, PRNGs are always going to be questionable. On the
>other hand, for cryptography, it is important that the person
>on the other end can produce the same numbers,
It is certainly true that stream-cipher cryptography depends on
reconstructing the sequence at both ends, and this is not possible
with a physically-random generator.
But physically-random generators *are* ideal for generating random
message key values or IV's or "nonce's" used in public-key protocols.
Message key values are simply enciphered and sent to the far end, so
the same value need not be generated there. (Or the message key is
sent as plaintext, then transformed in the same way by a keyed
enciphering or hashing on both ends.)
>and this means
>physically sending the numbers over a secure channel. In this
>case, a PRNG which is hard enough to crack, but simple enough
>to remember, has advantages.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Crossposted-To: alt.security,alt.privacy
Subject: Re: One-Time-Pad program for Win85/98 or DOS
Date: Sun, 28 Feb 1999 07:08:58 GMT
On Sat, 27 Feb 1999 21:24:49 +0100, in
<[EMAIL PROTECTED]>, in sci.crypt Helmut Kreft
<[EMAIL PROTECTED]> wrote:
>Daniel Kinnaer wrote:
>>
>>
>> I would like to know why you think a OneTimeKey is cryptographically
>> weak. Or is it just this implementation?
>>
>I do not say OTPs are cryptographically weak in general. A correct
>implementation is provably secure. In fact - it is guaranteed to be
>unbreakable.
I strongly disagree: The only OTP which is "provably secure" is the
theoretical *concept* of the OTP -- and that only protects theoretical
data.
When the OTP is reduced to practice, the theoretical assumptions --
such as the quality of the randomness in the pad, and the entropy of
pad and data -- no longer hold, but instead must be PROVEN. It is
these proofs which are not available to us.
Do we claim that the pad has more "entropy" than the text? Great!
Now prove it! (That would imply that we could measure the "true"
entropy, which is something we can only approximate.) Can we PROVE
that any real sequence generator has no fault which can be exploited?
I don't think so.
Anyone who thinks a practical OTP is "provably secure" should try to
write out a proof, then focus on what *can* be measured, and the
assumptions made in such measures. We can *assume* things which seem
reasonable, of course, but assumption is not PROOF.
>But a strong implementation must meet at least the
>following requirements:
>1.) A hardware random number generator must be used for key generation.
>2.) The key (pad) will have to be transmitted over a secure channel.
>3.) The key (pad) may be used only one time.
And not only that...
4) When there is a possibility that messages can be intercepted and
changed (e.g., on a store-and-forward computer network such as the
Internet), an OTP system *must* *not* be used to encipher any known
plaintext. That means no plaintext which comes from public media like
newspapers, magazines, press releases, etc.
5) If messages can be intercepted and changed, the OTP *must* *not* be
used to send multiple identical *plaintexts*, even under *different*
pads.
Here is why:
(4) (If The Opponents can ever acquire the plaintext for a message,
the usual OTP will reveal the pad immediately. This means that a new
message can be written using the revealed pad. This is the ability
for The Opponents to construct any message they want and send it under
our OTP, even though the pad has never been stolen or improperly
stored at either end.)
(5) (If The Opponents can obtain *one* of the plaintexts, then *every*
pad used to encipher those plaintexts becomes exposed. This is the
ability for The Opponents to construct any message they want for each
of those pads. Note that this exposes pads which have not been poorly
kept or exposed at either end. Neither end has any reason to question
the validity of the received message, because -- apparently -- neither
end has ever exposed their pad.)
Thus, OTP users can use an OTP in ways which seem to be very
reasonable uses of a cipher, but which in fact destroy OTP security.
This means that OTP users must be well-acquainted with the technical
details of OTP failure so that security can be maintained, but this is
a lot to ask of even knowledgeable users.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: "Daniel Feurle" <[EMAIL PROTECTED]>
Subject: need simple symmetric algorithm
Date: Sun, 28 Feb 1999 10:14:18 GMT
Hi everyone!
I am a student a in Database Systems Class at Technical University in
Vienna. There I do a project in engineering a simple DB application. In this
application I have a small table with products and its price. Now I want to
decrypt only the priceinformation field to the table and then to access to
this information only by my application. I need this becouse nobody should
be able to read this Information by accessing only the DB.
Therefore I need a simple symmetric algorithm to decrypt and encrypt this
number field which is only a 16-bit integer number.
Can anyone help me, or send me some Information about that.
I would really appreciate it,
thanks,
Dan.
------------------------------
From: [EMAIL PROTECTED]
Subject: Secure Elections?
Date: 28 Feb 1999 11:13:35 GMT
Reply-To: [EMAIL PROTECTED]
I have a copy of Bruce Schneier's "Applied Cryptography" 2nd. ed. It includes
a section on "Secure Elections" in Chapter 6. Have there been major advances in
that area since 1995 when that edition was published, or is it still a "moderately
accurate" picture of the state of the art, TODAY?
==============================================================
"I would predict that there are far greater mistakes waiting
to be made by someone with your obvious talent for it."
Orac to Vila. [City at the Edge of the World.]
===============================================
R.W. Hutchinson. | [EMAIL PROTECTED]
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Miller-Rabin prime test. Random bit size
Date: Sun, 28 Feb 1999 03:16:40 -0800
[EMAIL PROTECTED] wrote:
> "Erwin Molendijk" wrote:
> > When performing the Miller-Rabin test for prime n,
> > you have to choose a random number A, 2<= A <=n-2.
> >
> > Is it ok to choose a random A between 2 and the
> > max machine integer? (2 <= A <= 0xFFFFFFFF)
> >
> > (Ofcourse: n >> 0xFFFFFFFF)
> >
> > Btw, I choose A=2 for the first test.
> In my implementation of the M-R test I used a number (16) of the
> same small primes that I used to 'pretest' the candidate by division.
> If the number is a liar to a prime base, the chances are that it will be a
> liar to a base that is some multiple of that prime.
The issue is subtle. First, Erwin Molendijk definitely did
the right thing by using a base of 2 in the first test. When
generating crypto-size primes, this first test will in practice
catch all composites. If we profile the prime generation
routine, we find that the vast majority of time is spent in
this first test as it rejects dozens or hundreds of composites.
The number of small primes by which to sieve is not a sensitive
parameter. Most of the benefit of sieving is realized by
sieving the first couple dozen primes, and the time to sieve
doesn't become significant until using a thousand times as
many.
So back to the question: after the first test with a base of
2, should we do Miller-Rabin using small bases, or random
bases in [2..n-2] ? Well, in practice Robert G. Durnal's
method will work fine, but will not save any significant
amount of time. The base 2 test will catch all composites,
so the routine only performs further tests on the one
candidate that will finally be ruled prime.
In my opinion, since we only do more than one Miller-Rabin
test for certification (the second and later tests don't
actually weed out composites), we should use the test with
the strongest theoretical justification. I recommend
randomly chosen bases in [3..n-2].
--Bryan
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Unicity of English, was Re: New high-security 56-bit DES: Less-DES
Date: Sun, 28 Feb 1999 11:23:10 GMT
[EMAIL PROTECTED] wrote:
> Please see my previous reply a few minutes ago, where I analyze the two
> messages and show that the first message is much more probable. The fact that
> both appear to be in English was puzzling but it is actually neutral since
> the first is much more English-like. In fact, standard formalism applied to
> those two messages leads to only one answer, by what seems to be a large
> safety margin.
You missed the whole point of that exercise.
Neither message stands a chance of arising in normal English
conversation; they were specifically engineered as the solution
to a puzzle (find two very long near-English texts that are
isomorphic under simple substitution).
In fact, the "right" answer was determined arbitrarily by the
author of that little essay; it cannot be determined by any
logical analysis (since the messages are illogical to start with).
------------------------------
From: "Michael Scott" <[EMAIL PROTECTED]>
Subject: Re: Miller-Rabin prime test. Random bit size
Date: Sun, 28 Feb 1999 11:36:45 -0000
Bryan Olson wrote in message <[EMAIL PROTECTED]>...
>The issue is subtle. First, Erwin Molendijk definitely did
>the right thing by using a base of 2 in the first test. When
>generating crypto-size primes, this first test will in practice
>catch all composites. If we profile the prime generation
>routine, we find that the vast majority of time is spent in
>this first test as it rejects dozens or hundreds of composites.
>........
I agree. But be careful. As I recall from some experiments I once did, a
base of 2 misses all primes of the form 2^n-1. And such primes may be of
interest in for example Elliptic Curve based systems. But for random primes
this would not be a problem.
Mike Scott
______________________
Fastest is best. MIRACL multiprecision C/C++ library for big number
cryptography
http://indigo.ie/~mscott
ftp://ftp.compapp.dcu.ie/pub/crypto/miracl.zip - MIRACL Multiprecision
library
ftp://ftp.compapp.dcu.ie/pub/crypto/factor.exe - factor 80 digit numbers!
ftp://ftp.compapp.dcu.ie/pub/crypto/cm.exe - generate Elliptic Curves
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: New high-security 56-bit DES: Less-DES
Date: Sun, 28 Feb 1999 02:11:51 -0800
[EMAIL PROTECTED] wrote:
> You are drowning yourself in a glass of water. This whole sub-thread is
> really very simple: it is nonsense to talk about 'unicity distance' since it
> is not a 'distance'.
Unicity distance makes perfect sense because it is perfectly well
defined.
> But, I am sure the world is not going to turn any slower
> if you or Humpty-Dumpty call it whatever you guys like.
Us guys? It's part of the technical terminology of the
discipline.
> > > But, you still did not answer my didactical question. I will pose it again:
> > > "What is the distance of your hand?"
> >
> > I believe the question is nonsense.
>
> Agreed, Bryan. That is why I asked four questions in sequence, that one being
> the first. But, since you evidently missed out that clue and snipped out the
> last three, I will reinstate their didactical order for you (btw, note the
> word "didactical" used above -- that question was posed in order to induce a
> lesson). The next didactical question was:
My question to you was didactical too, and served to answer the
issue in all four of yours. My question was: Do you know what
a term of art is?
> > > Note that this question is analogous to ask: "What is the unicity distance
> > > of cipher C?"
>
> Which, likewise the first, is nonsense... so, it is nonsense to ask about the
> unicity distance of a cipher in the same way that it does not make sense to
> ask what is the distance of your hand. Got it?
The "it" that I get is a misunderstanding of terms of art. Unicity
distance is well defined in cryptology. Just think of it as one
term, not two words. I'm not aware of any definition for the
distance of a hand.
I heard an orthopedist talk about the "velocity" of a fracture
to a patient's knee. I could tell he did not mean its speed
and direction. (I'm still not fully clear on what that does
mean.) Had I not heard it from a doctor, I would not have
guessed that the velocity of an injury makes any more sense
than the distance of a hand. But he was not talking nonsense;
he was using the technical terminology of his field. When I
write "unicity distance", I'm using the technical terminology
of my field.
I gather there is also some specialized usage of "I won't
quibble" vastly different from its common interpretation.
--Bryan
------------------------------
From: [EMAIL PROTECTED] (Wei Dai)
Subject: Re: ElGamal key generation
Date: Sun, 28 Feb 1999 02:32:27 -0800
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
> Wei Dai wrote:
> > p of 768 bits give you at most 72 bits of security (i.e. best known
> > attack takes about 2^72 operations),
>
> What is the best known attack?
>
> Please give me a reference book title or website I can read which can
> explain in greater detail where you reached the conclusion that it takes
> 2^72 operations to solve the discrete log problem over a finite field for
> a 768 bit modulus.
Quoting http://www.certicom.ca/ecc/wecc3.htm:
As in the case with factoring, the best current algorithm known for the
DLP is the number field sieve [16, 33]. It has precisely the same
asymptotic running time as the corresponding algorithm for integer
factorization. This can loosely be interpreted as saying that finding
logarithms in the case of a k-bit prime modulus p is roughly as
difficult as factoring a k-bit composite number n.
So the 2^72 number comes from the number field sieve asymptotic formula,
with constants extrapolated from a table of experimental running times
in Odlyzko's "The Future of Integer Factorization" at
ftp://ftp.rsa.com/pub/cryptobytes/crypto1n2.pdf, and also taking into
account the factoring of RSA-130. You could argue that these constants
are derived from factoring experiments and don't apply to discrete log,
but unfortunately I'm not aware of any discrete log experiments using
the number field sieve.
The exact formula I used, expressed in C is:
(2.4 * pow(n, 1.0/3.0) * pow(log(double(n)), 2.0/3.0) - 5)
where n is the bit length.
> Is each "operation" a multiplication or some other operation which is
> much more expensive?
It's a 32-bit word operation.
> With a workstation with 100 mega operations per second it takes 4*10^15
> seconds to do 2^72 operations. That is 1 million years, or one year, if
> you have a million workstations.
That seems about right. But keep in mind that processing power per
dollar doubles about every 12-18 months, so in 10 years it might take
only 1000 workstations one year to do 2^72 operations.
> >and less if your attacker knows
> > some algorithmic improvements in factoring that is not yet public. I
Of course I meant to say discrete log here instead of factoring.
------------------------------
From: Paul Crowley <[EMAIL PROTECTED]>
Subject: Re: Testing Algorithms [moving off-topic]
Date: 28 Feb 1999 10:51:46 -0000
Darren New <[EMAIL PROTECTED]> writes:
> > > Think of it this way -- what's the minimum amount of energy necessary
> > > to move a brick five feet (horizontally)?
>
> One photon?
A photon of what energy? Are we talking gamma rays or radio waves?
--
__
\/ o\ [EMAIL PROTECTED] http://www.hedonism.demon.co.uk/paul/ \ /
/\__/ Paul Crowley Upgrade your legacy NT machines to Linux /~\
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: A New Public-Key Cryptosystem
Date: Sun, 28 Feb 1999 02:36:28 -0800
Cryptoad wrote:
[...]
> I think the
> essence of the Craig query is this: can one with a reasonable work factor
> reverse a nonsingular mapping (encryption) achieved by a rectangular "public
> key matrix (PKM)" ? In such a system, bit states in the plaintext select rows
> in the PKM which are XOR'd to produce the ciphertext. The plaintext can be
> recovered with secret private key information (not shown in his example).
> However, if the rows which were selected to produce the ciphertext can be
> computed solely from the PK M and the ciphertext, then the system is manifestly
> insecure.
I guess that gives me a well defined problem: given m bit vectors
each of length n, and a single bit vector x of length n, find a
subset of the m vectors that sum (under xor) to x.
If a solution exists, we can find one easily with Guasian
elimination.
In Craig's proposal, he seemed to imply some non-linear operation
built into the computation, but he wasn't specific. From what I
have been able to gather, I don't see that the non-invertability
of a rectangular matrix adds any security. In the problem as I
state it above, if m=n and the matrix is non-singular, then for
any x there is exactly one solution. If m!=n it's still no
harder to find solutions if they exist.
--Bryan
------------------------------
From: BRAD KRANE <[EMAIL PROTECTED]>
Subject: Re: True Randomness - DOES NOT EXIST!!!
Date: Sun, 28 Feb 1999 00:01:20 GMT
Bill Unruh wrote:
> Unfortunately you seem not to have heard of physics developed 100 years
> ago, called quantum mechanics. Two identical system, set up identically
> will not give the same results in the future.
Being identical does include the most important element of all time.
~NuclearMayhem~
>
>
> In <[EMAIL PROTECTED]> BRAD KRANE <[EMAIL PROTECTED]> writes:
> ] True randomness does not exist. It always depends on some variable
> ]at some *FIXED* time. FIXED times are not anywhere near random.
> ]**EVERY** thing that goes on in the universe is hapening because of all
> ]the forces of **EVERY** thing else in the entire universe. If you where
> ]to take mesurements at one place in time in one universe and recorded
> ]it. Then lets say you where able to re-create exactly the universe you
> ]where just in some where else and you took the exact same measurement
> ]the so called random number that you recorded before would be the exact
> ]same as though you took the measurement in the first universe. As
> ...
------------------------------
From: [EMAIL PROTECTED] (Herman Rubin)
Subject: Re: Testing Algorithms
Date: 28 Feb 1999 07:25:14 -0500
In article <[EMAIL PROTECTED]>,
Trevor Jackson, III <[EMAIL PROTECTED]> wrote:
>fungus wrote:
>> "Trevor Jackson, III" wrote:
>> > There is no minimum energy per reversible computation. There is a
>> > minimum energy per irreversible computation. Between these two true
>> > statements lies lots of room for misunderstanding.
>> *something* has to trigger a change of state...
>Yes. There is no claim to perpetual motion. Every state change has to be
>driven by some expenditure of energy. But, there is no limit on how small
>that amout of energy can be when the computation is reversible. Thus, it
>can be arbitrarily, ridiculously small. Efffectively zero even though not
>actually zero.
This is off-topic for this group, but it still needs addressing.
The problem is NOT to produce state changes with extremely low
energy; this is not difficult. It is to produce state changes
which will not reverse spontaneously or from transient noise.
A "permanent" magnet illustrates the situation; it has a large
hysteresis loop, which means that most of the energy in changing
its state goes off in heat, but this keeps it stable. Computer
memory, and also the state of more accessible units, is like this;
changeable, but not too easily so. The latter is what is needed
to keep it from being lost.
--
This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
[EMAIL PROTECTED] Phone: (765)494-6054 FAX: (765)494-0558
------------------------------
From: "Jay" <[EMAIL PROTECTED]>
Crossposted-To: alt.privacy,talk.politics.crypto
Subject: Re: Can the quantum computer determine the truth from a lie?
Date: Sun, 28 Feb 1999 07:46:03 -0500
You seem to be confused as to what quantum computing can or cannot do.
(That's ok, there are still a lot of questions). However:
Anthony Stephen Szopa wrote in message <[EMAIL PROTECTED]>...
>
>Then I encrypt the message. My recipient has the key that will not only
>decrypt the message but remove all the random noise as well.
>
>How will the quantum computer determine the correct intelligence
>communicated from what was essentially a message that lied?
No one is claiming this.
>As far as good encryption is concerned, quantum computers pose no real
>threat.
>
>The idea that by inputting an encrypted message into a black box quantum
>computer and that it will absolutely output the correct encrypted
>message is preposterous.
>
The threat is real, but depends on the type of encryption. OTP theoretically
have large numbers of possible decryptions, so there is little that can be
solved here by strict computation (just like in the current world). OTPs,
however have enough other problems to make them mostly useless.
Key based encryption, whether DES, 3DES, Blowfish, etc. are at risk, because
most keys will result in no valid message. QC can reduce the number of
messages to examine enormously and quickly (this is how DES was
cracked...imagine a 3DES cracker that can test all solutions in a few
seconds).
Public key systems could possibly be attacked on the basis that most
possible keys are not valid keys and can quickly be thrown out if they can
be checked fast enough.
All that having been said, however, we still don't know that QC will work
for non trivial problems.
...Of course, we still will have to worry about molecular computing, which
does not invoke spooky questionable theoreticals, and is much closer to
reality. DNA type computation would be ideal for decryption analysis.
Jay
------------------------------
** 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
******************************
