Cryptography-Digest Digest #831, Volume #9 Mon, 5 Jul 99 09:13:05 EDT
Contents:
Re: Quantum Computers ("rosi")
Re: Quantum Computers (Anti-Spam)
Re: How do you make RSA symmetrical? ([EMAIL PROTECTED])
Re: I don't trust my sysadmin (Eric Hambuch)
Re: Crypto Books on CD-ROM (David Parkinson)
Summary of 2 threads on legal ways of exporting strong crypto (Mok-Kong Shen)
Re: Encrypting software in the movie "The Saint"??? ([EMAIL PROTECTED])
Re: RSA Padding ([EMAIL PROTECTED])
Re: How do you make RSA symmetrical? ([EMAIL PROTECTED])
Re: MP3 Piracy Prevention is Impossible (Andrew Haley)
Re: Why this simmetric algorithm is not good? ([EMAIL PROTECTED])
Re: The Constrained One-Time Pad and the Cryptanalyst's Lucky Day ("Dr.Gunter Abend")
----------------------------------------------------------------------------
From: "rosi" <[EMAIL PROTECTED]>
Subject: Re: Quantum Computers
Date: Mon, 5 Jul 1999 00:15:14 -0400
Thank you very much, David.
I am torn a bit between saying a bit more or just leave it alone. It could
be
too far away from what this thread was intended and get messy.
I have no knowledge in QC(rypto) and only have a somewhat vague
notion of 'QKD'. There are questions we could ask. For example,
obviously, how do we know the Q channel and the open channel are
not both taken over, how can we be sure a Q source shooting a photon
to each of the two parties of interest do not shoot out four more (or
however many more as the number of polarizations), etc.
When the secret is distributed, do we use it in a Q fashion or 'ordinary'
fashion? Do we use it one time? (too practical maybe) Bottom line:
I still need to be shown a more sensible, fundamental 'distinction'
between the way this authenticated transmit in Q fashion and any other.
I can not take it out of context. This thread was asking the question:
should QC(omputers) exist, any non-doomsday other than IT? We have
this post. Not a solution. Sorry, if I went too far but hope my point is
clear.
Thanks again, David, for your wonderful posts on this topic.
--- (My Signature)
David A Molnar wrote in message <7lo7hn$tjf$[EMAIL PROTECTED]>...
>rosi <[EMAIL PROTECTED]> wrote:
>> ???
>
>I think he's referring to what could be called
>"quantum key distribution." Otherwise expanded on
>in the post which covered reliable couriers.
>Don't take my word for it, though - he gave URLs.
>
>-David
>
>
>> --- (My Signature)
>
>> Anton Stiglic wrote in message ...
>>>In a Quantum World, Quantum Crypto is unconditionaly secure.
>>>In fact, Quantum Crypto is already publicaly implemented
>>>(Los Alamos and other places). It is much easier to implement
>>>than a Quantum Computer (it's not the same thing at all either).
>>>
>>>See my labs page: http://crypto.cs.mcgill.ca
>>>+ my directors page: http://www.cs.mcgill.ca/~crepeau
>>>
>>>Anton
>>>
>>>
>
>
------------------------------
Date: Sun, 04 Jul 1999 22:26:19 -0700
From: Anti-Spam <[EMAIL PROTECTED]>
Subject: Re: Quantum Computers
Greg Ofiesh wrote:
>
> > If we use cryptosystems "orthogonal" or independent of those
> > QC-acceptable algorithms attacks, then our cryptosystems are immune.
> > QCs pose no threat if we are careful.
>
> So, would you say that either DLP or ECDLP problems are immune from
> QCs? How about the idea that QCs once developed sufficiently can
> perform massive parallel computations? Then does any algorithm appear
> immune to a QC? Just want to get your feel on this.
>
> Sent via Deja.com http://www.deja.com/
> Share what you know. Learn what you don't.
As a follow-up to my original post, here's a snippet that explains well
the situation we face with QC cryptanalysis, from "Explorations in
Quantum Computing":
"Quantum parallelism allows you to compute an exponential number of
functional evaluations in the time it takes to do just one functional
evaluation classically. Unfortunately, the laws of quantum mechanics
make it impossible to extract more than one of these answers explicity.
The problem is that although you can indeed calculate all the function
values from the tape [book is making a comparison to a classical Turing
Machine], you will only obtain one of the many outputs. Worst still, in
the process, the information about all the other inputs is lost
irretrievably. So the net effect is that you are no better off than had
you used a classical Turing Machine. So, far a functional evaluation
goes, the quantum computer is no better than a classical computer."
Why then use QCs? QCs CAN calculate "certain joint properties of all of
the answers without having to reveal any one answer explictly." The
book gives an example.
"Suppose there is a function f that can receive one of two inputs, 0 and
1, and that we are interested in computing the XOR of both function
values, that is f(0) XOR f(1). The result could be a decision as to
whether to make some particular stock investment tomorrow based on
today's closing prices. Now suppose that, classically, it takes 24 hours
to evaluate each f. Thus if we are stuck with a single classical
computer, we would never be able to compute the XOR operation in time to
make the investment the next day. On the other hand, using quantum
parallelism, Deutsch showed that half the time we would get the
guaranteed correct value of f(0) XOR f(1). Thus the quantum computer
would give us useful advice half the time and never give us wrong
advice."
(The Deutch reference is "Deutsch D. "Quantum Theory, the Church-Turing
Principle, and the Universal Quantum Computer," Proceedings Royal
Society London, Vol. A400 (1985) pp.97-117.)
Note we are getting information about a joint property of f(0) and f(1),
but we learn nothing about what f(0) is aside from f(1), or what f(1) is
aside from f(0). Let f(0) XOR f(1) = X. Suppose we ran this
hypothetical QC on this hypothetical problem and the answer is X = 1.
Well, f(0) = 1 and f(1) = 0 results in X = 1. So does f(1) = 0 and f(1)
= 1. We also know that they both cannot be zero and they both cannot be
one. BUT, we cannot say for sure what the value of the functional
evalution with 0 as input was, and we cannot say what the functional
evaluation with 1 as input was. We can only know things about a joint
property of these two functional evaluations.
Shor's algorithm for factoring integers relies on this feature. We want
to factor an integer n. The algorithm applies the same functional
evaluation, f(a) = ( x exp a ) mod n, where x is a random integer
coprime to n, to a large number of integers K less than n. It turns out
that f(0), f(1), f(2),....f(K) is periodic. As we evalute a large
number of arguments to f(a), we find that the results of f(a) begin to
repeat with a period r. Well, the resulting end state of the quantum
calculation (due to quantum interference) is a joint property of all of
those simultaneous functional evaluations, and is an integer multiple of
the period r. All of those individual evaluations of the f(a) function
are related by this common period r, and that is the joint property of
the myriad evalutions that comes out of the interference of all of the
superimposed quantum states in the QC mapped to represent the f(a).
If we can't find a way to answer our question in the form of a joint
property of numerous valuations of a function f, then the QC cannot
calculate and answer our question.
If we can't find a way to map the result of a cryptanalysis of a
ciphertext in the form of a joint property of numerous valuations of the
cryptanalysis function crypt(ciphertext), then the QC cannot calculate
the answer to the cryptanalysis question.
There's the research area.
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: How do you make RSA symmetrical?
Date: Mon, 05 Jul 1999 07:38:47 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Gilad Maayan) wrote:
> I'll probably be hammered for my stupidity, as in previous posts, but
> I'm asking it anyway. Is there anyway to make RSA symmetrical? In
> other words, to take, say, a 64-bit message, encrypt it with a
> 1024-bit key and get a 64-bit cyphertext, and then decrypt that, and
> get back to your original 64 bits? I'm aware of the small keyspace
> this would result in (you'd only have to check 2^64 possible
> cyphertexts, etc.), but in my case, the ambiguity factor would make up
> for this shortcoming.
Although I did not like the way you have answered some people's
comments, I will show you a way to achieve what you require. It will
probably be something which we can no longer call RSA, but it is using
the same underlying principle.
If you encrypt a message using the RSA scheme, you are almost likely to
end up with some cyphertext which will be about the same length as the
modulus. You cannot do anything about this. However, we can ask the
question: "Is there any value v, such that
m^e == c (mod N)
c == c' (mod v) [or c=k*v+c']
c'^d == m' (mod N)
m' == m (mof v)
Quite tricky. If you expand (k*v+c')^e, you will see that the only way
you can achieve these four equations is for v=p, or v=q when N=p*q.
Not a very good result eh? You have two modulus' and one of them is the
factor of the other. Hmm.
Well, I think (I have not thought about the following for too long, but
it seems possible), we can expand the current scheme to let you have
some degree of security left. At least there is no OBVIOUS weakness
that I can see with the following.
1. choose THREE prime numbers p, q, r such that r has lm+1 bits, where
lm is number of bits in your messages; p, and q has (1024-lm-1)/2 bits.
2. let the modulus, N, be N=p*q*r
3. Let lambda = lcm(p-1, q-1, r-1)
4. Choose an arbitrary e, which is coprime to lambda, and calculate d
to satisfy
e*d == 1 (mod lambda)
5. Encrypt using C=(M^e mod N) mod r, C will have at most lm+1 bits
6. Decrypt using M=(C^d mod N) mod r [I hope this will always be
correct]
Here is an example I have done using random numbers:
p=13815475050774689867
q=12560510791140164603
r=65537
N=11372597825296919342777861723404631924544137
lambda=11372424295873459357843725235174855365885952 [I did not use lcm
() for this example. It is (p-1)*(q-1)(r-1)]
e = 65535
d = 10922455634864839839801628957845056022577151
M = 12345 (<65537)
C= (M^e mod N) = 6140009077969454130220750827132812728305506
C'= (C mod r) = 31651
M' = (C'^d mod N) = 226071908133054616845508940606134189469823
M = (M' mod r) = 12345
Well, as you can see it worked for an (almost) random example. :-) It
sounds correct. The only thing left is whether you can trust this one,
or not. The public key (e, r, N) is not enough to correctly determine
the private key (d, r, N), because you still have a (presumably) large
N/r to factor in order to obtain lambda. Hovever, you whave one of the
factors in the public key, and it is enough information to make people
lose sleep over. :-)
And lambda is a multiple of r-1.
I hope you won;t use this until someone more knowledgeable than me can
verify that this will always work, and it is not too weak to be used.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Eric Hambuch <[EMAIL PROTECTED]>
Subject: Re: I don't trust my sysadmin
Date: Mon, 05 Jul 1999 10:57:23 +0200
[EMAIL PROTECTED] wrote:
>
> In article <[EMAIL PROTECTED]>,
> "David N. Murray" <[EMAIL PROTECTED]> wrote:
> > Greetings, all:
> >
> > I'm in search of a protocol to implement the following scenario:
> >
> > I have an automated task that connects to a database.
> > The database requires a username/password combination.
> > I need to store the username/password with the automated task.
> > My system administrator (who needs to be able to read the
> > automated task to do backups) is not authorized to access
> > the database. (Protecting the database is not my concern.
> > Just protecting the automated login.)
>
> Hash the password and store the hash on the protected side. So you
> type the password on Machine A, it gets hashed goes thru the middle man
> and compared with the HASH on Machine B.
>
> Unless the sysadmin can get access to stuff you type (which I doubt
> they can) they will not be able to tell what the password was.
As far as I know, "root" can access everything you type on the console
?!
Eric
------------------------------
From: David Parkinson <[EMAIL PROTECTED]>
Subject: Re: Crypto Books on CD-ROM
Date: 5 Jul 1999 09:10:11 GMT
Michael D T Clark <[EMAIL PROTECTED]> wrote:
<snip>
: There is indeed a catch. Those of us living outside the USA cannot buy
: the CD, because it is a restricted export.
: I would really like to get a copy to compliment the books I already
: have, but can't get it until the export restriction are lifted.
: Michael Clark
: mclarkatsoutherndotcodotnz
Is it? I had no problems at all in buying a copy and
having it shipped here (UK).
David
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Summary of 2 threads on legal ways of exporting strong crypto
Date: Mon, 05 Jul 1999 10:48:38 +0200
I presume that the results todate of discussions in two threads in
sci.crypt that I recently initiated are of sufficient value and
significance to justify a summary being given to them.
To export strong crypto, it is surely o.k. if one has one's paper sent
to a country without crypto laws for placing (by a foreign subject) on
a server and gives the reference (URL minus the prefix http://) to it
on one's domestic home page so that any reader can access the content
of the paper without much effort. Probably providing a link, i.e.
employing the full URL for mouse click, is also o.k. This needs
in my humble view to be clarified ín order to to be absolutely sure.
Using the reference only is, however, conservative and can't get in
conflict with laws in any case.
The other (much more inconvenient yet do-able) way of exporting strong
crypto is to use Boris Kazak's method to encode the stuff, i.e.
taking any text and employing lower case for representing 0 and upper
case for representing 1, and put the resulting English text directly
on one's site. In this case the reader has to write a tiny program to
retrieve the stuff but the author needs no assistance from a foreign
server. (The tiny program is exportable and can be easily made
publically available.)
Thus I conclude that one can indeed manage to export strong crypto
(now!) irrespective of the ultimate outcome of the Bernstein case.
Of course, we hope that the bureaucrats' attempt for a revision
wouldn't succeed. I strongly believe that the above could be of some
significance, should a revision of the case take place.
Finally it may be of value to note as a aside that Boris Kazak's
method is effective for jamming the WWI if sufficient people on the
internet regularly encode meaninless random bits into their e-mails
that way.
M. K. Shen
========================
http://www.stud.uni-muenchen.de/~mok-kong.shen/ (Updated: 12 Apr 99)
(Origin site of WEAK2-EX, WEAK3-EX and WEAK4-EX, three Wassenaar-conform
algorithms based on the new paradigm Security through Inefficiency.)
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Encrypting software in the movie "The Saint"???
Date: Mon, 05 Jul 1999 11:29:01 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Maze) wrote:
> Hi,
> One of my favorite movies is "The Saint" with Val Kilmer.
> My guess is that you have seen it. I'm a little curious in the
software
> that he (The Saint) is using on his Apple PB5300c. Especially the
> encrypting software he's using to communicate with the Russian bad
guys. I
> like the part when he is encrypting a picture file and you see the
picture
> transforming into some blurred image and loads into an email as a
> attachment.
> My question is: Does this software exist or is it just fiction?? I
mean,
> the other stuff he uses is a little to good to be true. Like when he
> transfers pictures taken with his digital camera onto the powerbook.
Takes
> him a couple of seconds to do this when in reality it takes a bit
longer.
>
> Do you have any clues to as if this encryption software exists??
I like that movie too. You have to remember that all they do in movies
is for effect. There is software to encrypt email attachments and
emails. Check out www.pgpi.com. With this you can send encrypted
email/files etc...
Normally you don't look at encrypted text because it SHOULD be white
noise... PGP for example does not show the plaintext being encrypted
(although it might be a neat effect).
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: RSA Padding
Date: Mon, 05 Jul 1999 11:25:51 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (S.T.L.) wrote:
> How is frequency analysis done on an RSA message? I've never heard of
frequency
> analysis being applicable to RSA, only chosen-plaintext attacks.
Encrypt a message with RSA in byte size blocks and I will crack your
message in under a day...
You have to put random padding for the same reason people like CBC and
PCBC mode for block ciphers. If you only have a one byte message but
20 bytes of random padding the ciphertext is not going to be the same
when the one byte message is the same. Thus you cannot analyze it that
way.
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: How do you make RSA symmetrical?
Date: Mon, 05 Jul 1999 11:40:29 GMT
In article <7lpne7$e5g$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Although I did not like the way you have answered some people's
> comments, I will show you a way to achieve what you require. It will
> probably be something which we can no longer call RSA, but it is using
> the same underlying principle.
>
> If you encrypt a message using the RSA scheme, you are almost likely
to
> end up with some cyphertext which will be about the same length as the
> modulus. You cannot do anything about this. However, we can ask the
> question: "Is there any value v, such that
> m^e == c (mod N)
> c == c' (mod v) [or c=k*v+c']
> c'^d == m' (mod N)
> m' == m (mof v)
>
First off. ***THE PLAINTEXT AND CIPHERTEXT ARE THE SAME SIZE*** You
have padding on the plaintext for short messages so that they are
always the same length.
Second no v exist where v != pq which will decrypt a message. This is
because what if v is smaller? Then you have pq - v messages that will
not decrypt (they will have two solutions). Same if v > pq...
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (Andrew Haley)
Subject: Re: MP3 Piracy Prevention is Impossible
Date: 5 Jul 1999 12:40:38 GMT
Harvey Rook ([EMAIL PROTECTED]) wrote:
: Water marks that survive digitial to analog to digital conversion,
: do exist. Essentially what you do is take a fourier transform of
: the song, tweak the transform, and then calculate the inverse
: fourier transform.
That may be one way of doing it, but it's not the only way. One of
the most important patents is Solana's US05687191 (Liquid Audio) which
uses direct-sequence spread-spectrum encoding. This technique has the
advantage that all it does to the music is very slightly raise the
noise floor, so it's likely to be inaudible.
See also US05822360.
Andrew.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Why this simmetric algorithm is not good?
Date: Mon, 05 Jul 1999 12:35:41 GMT
<snip>
If your PRNG is truly random you have invented a 128-bit OTP. This
appears to be a stream cipher for large blocks. Normally stream
ciphers are byte wise or bit wise. This is because stream ciphers are
primarly for encoding variable length messages.
If you post your ?RNG? or PRNG we could actually comment on the
strength of the algorithm.
Tom
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: "Dr.Gunter Abend" <[EMAIL PROTECTED]>
Subject: Re: The Constrained One-Time Pad and the Cryptanalyst's Lucky Day
Date: Mon, 05 Jul 1999 15:15:16 +0200
Reply-To: [EMAIL PROTECTED]
Lincoln Yeoh wrote:
> Given a totally random generator running for an eternity,
> eventually you may get Shakespeare. But it's still random.
>
> But if you're still concerned just compress the plaintext.
> So even if the OTP has a long string of zeroes somewhere
> they aren't going to extract it as easily.
In another thread ("The One-Time Pad Paradox"), I suggested to
modify the algorithm in the following way:
If the ciphertext contained some intelligible phrases, one
should repeat the encryption with a somewhat modified plaintext.
Automatic determination of "intelligible phrases" could be done
by checking the presence of more than 10% tripletts of letters
with at least one vowel. Random streams of ciphertext would
contain about 0.4% tripletts of this kind, thus you have to omit
the initial ciphertext not very frequently. The bias introduced
by this technique should be quite low.
Several posters refused this attempt with just the argument
"it's still random", "it doesn't leak any information", etc.
That's all true, but it doesn't hit the point J.Savard was
asking ("if a cryptanalyst ... guesses the correct plaintext,
this would lead to catastrophic consequences").
No matter *how* a readable message is produced accidentally,
and if it is the real plaintext or any other one of the huge
amount of possible but misleading texts, the adversary might
assume that a mistake has revealed just the truth.
You never can avoid that an adversary might guess the truth.
Already the *existence* of a message gives him some hint.
And if he tries to cryptanalyze it he may accidentally get
something readable. But, the higher the effort to get it, the
lower the probability that he believes it. Only if it is simply
visible, he may take it for true -- because accidentally there
could be no encryption at all or a malfunction of a usually
strong cipher.
Ciao, Gunter
------------------------------
** 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
******************************
