Cryptography-Digest Digest #288, Volume #14 Thu, 3 May 01 17:13:01 EDT
Contents:
Re: 1024bit RSA keys. how safe are they? (Lawrence Kirby)
Re: Message mapping in EC. (Mike Rosing)
Re: Random and not random (Matthew Skala)
Re: Random and not random (Matthew Skala)
Re: DL blind signature ("Cristiano")
Re: Message mapping in EC. ("Cristiano")
Re: A Question Regarding Backdoors ("Tom St Denis")
Re: Message mapping in EC. (Doug Kuhlman)
Re: Ciphertext only (John Myre)
Re: Message mapping in EC. ("Cristiano")
Re: Ciphertext only (Jeffrey Williams)
How much math is required to study this? ("Paradigm")
Re: Random and not random (Mok-Kong Shen)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Lawrence Kirby)
Subject: Re: 1024bit RSA keys. how safe are they?
Date: Thu, 03 May 2001 15:43:26 GMT
Reply-To: [EMAIL PROTECTED]
In article <9chso8$fjh$[EMAIL PROTECTED]>
[EMAIL PROTECTED] "Scott Fluhrer" writes:
>
>Tom St Denis <[EMAIL PROTECTED]> wrote in message
>news:udYG6.92831$[EMAIL PROTECTED]...
>> -----BEGIN PGP SIGNED MESSAGE-----
>> Hash: SHA1
>>
>> "Dopefish" <[EMAIL PROTECTED]> wrote
>> in message news:[EMAIL PROTECTED]...
>> > virtual memory?
>>
>> Hmm? PC's (x86's that is) can't address the required memory.
>
>To be pedantic, they can. Remember, an x86 (for x>=3) really has 48 bit
>virtual addresses, and while that capability isn't typically used, it's
>still there.
IA32 has a 32 bit data path into the page translation hardware so
all segments must exist in the same 4GB address space. It isn't like
the 8086 and 80286 where segments allowed a 16 bit program to address
1MB and 16MB memory. Different processes can have distinct 4GB address
spaces but it would be a nightmare to use that sort of model to address
large amounts of memory.
--
=========================================
Lawrence Kirby | [EMAIL PROTECTED]
Wilts, England | [EMAIL PROTECTED]
=========================================
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: Message mapping in EC.
Date: Thu, 03 May 2001 12:26:50 -0500
Cristiano wrote:
>
> I use the curve 160 r1 from "SEC 2: Recommended Elliptic Curve Domain
> Parameters", p is a 160 bit number (2^160-2^31-1).
> If I start with m=84894A24.... (these are the firsts 32 bits of 160) it
> doesn't map until m=6 84894A24... (163 bits). Is it good that m>p map on the
> curve?
In principle it doesn't matter. If you shift your data up so the least significant
bits are flipped instead, or pick some place in the middle, you still are "randomly"
selecting points that hold your data. In this case you got lucky, it fit with only
3 bits :-)
> You need 5 bits to make sure data will fit on the curve, so that
> leaves plenty for raw data.
>
> Is this only an aproximate measure or does it have some explanation?
It's empirical observation. A company wanted to make sure their registration
system would work, and I suggested that 4 bits was enough. So they ran a test,
and in 10 million tries they found 5 errors. So we went with 5 bits. After 60
million tries there were no errors, i.e. all data was recovered since it fit
on the curve.
The explanation has to do with the density of points. For any x value, there
is some radius measured in hamming weight which will find an x value which is
on the curve. I am not sure any mathematician has looked at the problem as it
would be a rather hard one to prove. Empirical proof works in the real world,
so I'll accept it :-)
Patience, persistence, truth,
Dr. mike
------------------------------
From: [EMAIL PROTECTED] (Matthew Skala)
Subject: Re: Random and not random
Date: 3 May 2001 10:24:11 -0700
In article <[EMAIL PROTECTED]>,
John Savard <[EMAIL PROTECTED]> wrote:
>This is true. However, I add to my reply in this thread in my post "On
>the Validity of Non-Logical Modes of Thought" that it's OK to have
>this failure mode under certain circumstances, but not others.
I did read your post on that, and was sorry no-one replied to it because
it's an interesting idea - as cryptographers we have a definition of what
it means for communications to be secure, but maybe our clients have a
different definition that we cannot change. As ethical professionals we
have some obligation to give them real security... but we also have to
make our clients feel that they're getting what they asked for.
Now, what if we told General Jones:
Okay, you can use a constrained OTP, but you have to use *two* of them.
Crypto Clerk Carol takes the original plaintext, applies a constrained OTP
to it, and gives the result to Crypto Clerk David, who doesn't know the
original plaintext. Carol knows that the plaintext was secure when it
left her hands, even if she doesn't understand all the details of how an
OTP works. Crypto Clerk David applies a second constrained OTP to it,
yielding the ciphertext that is transmitted.
David knows that the plaintext was secure when it left his hands, because
he took the already-encrypted message from Carol, which was recognizably
gibberish. Even if he doesn't understand all the details of how an OTP
works, he can understand that even if the ciphertext he transmits looks
like *a* plaintext, there is no way he can be sure that it was the *real*
plaintext because it could just as likely be anything else that looks like
a plaintext. He has no reason to go home thinking "Gee, it was my bad
luck of getting a bad pad that doomed that spy to being captured by the
enemy" because he doesn't know whether the message he transmits that says
"The spy is hiding at 1234 Any Street" is the real plaintext or not. As
far as David knows, it could as likely be 4321 Any Street, or 9482 Foo
Street, or the message could have been about something else entirely.
It's sort of like the tradition of loading one of the firing-squad's guns
with a blank... every man in the squad can at least have the consolation
that he doesn't know *for sure* that he shot the prisoner.
The trick, of course, is that we construct our bad-pad-rejection test for
the constrained OTP such that even though *one* constrained pad isn't
uniformly distributed over the space of all possible pads, the composition
of *two* constrained pads is uniformly distributed. This shouldn't be
difficult to do. Carol and David together have the effect of applying one
true OTP, but nobody ever has to use an all-zero pad and come to grips
with the worries such a pad might give them.
We still face some issues of educating General Jones, because he's smart
enough to be aware that the ciphertext coming from David could be the same
as the plaintext going to Carol. Maybe he's going to object to that
possibility. If he does, then there's no way to save the perfect secrecy
property of the OTP. But if Carol and David are both doing their duty,
which includes not talking to each other about the content of the
plaintext and ciphertext, then should such a situation occur, *nobody will
ever know* that the plaintext was equal to the ciphertext. General Jones
can honestly say that nobody in his army ever knowingly transmitted a
ciphertext that was equal to the plaintext or equal to any trivial
encryption of the plaintext.
--
Matthew Skala
[EMAIL PROTECTED] "I fish stranger things than you
http://www.islandnet.com/~mskala/ out of my granola every morning."
------------------------------
From: [EMAIL PROTECTED] (Matthew Skala)
Subject: Re: Random and not random
Date: 3 May 2001 10:46:18 -0700
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>infinite source. So suppose one employs a statistical
>test to discard some segments of the sequence output from
>the source. We can first consider that these segments are
>employed to encrypt some dummy (unimportant) messages and
>one actually sends them together with the proper messages
>that are encrypted with the remaining segments of OTP that
It's not good enough for an OTP to be randomly generated. It must be
randomly generated *and* independent of the plaintext. If it's not, then
you lose perfect secrecy. If you send different plaintexts, or the same
plaintexts in a different order, depending on the results of statistical
tests on the pad, then your plaintext and pad are not independent, and you
lose the perfect secrecy property. You'll probably need some way of
communicating which pads were discarded or used for dummy messages, but
we'll ignore that; I don't think that's a difficult problem to solve.
If you do use the bad pads for dummy messages instead of discarding
them, then you still have a bad pad problem. Suppose I generate a bad pad
segment that just happens to be equal to my secret message XORed with the
dummy message I was going to use. That will probably fail the statistical
tests (XOR of two plaintexts tends to still have low
statistically-measured entropy) so I will use it for my dummy message...
and end up transmitting my secret message unencrypted!
It gets worse. Suppose my pad, XOR whatever I'm going to XOR it with,
happens to correctly predict the secret message that I'm going to want to
transmit some time next week. At this point, I don't even *know* that
it's a bad pad... but if I use it, I will be transmitting, unencrypted, a
secret that I will want to keep from my enemy.
Suppose I'm so frightened of bad pads that I don't transmit any messages
at all. I just encrypt them and throw them away. But my enemy is running
a random pad generator too and it just by random chance happens to
generate my stream of plaintext! Now my friends don't get the message
because I was so afraid that I didn't send it, but the enemy *does* get
the message! Oh, horror! What can we do about this?
I really don't think there is any way around the bad pad "problem", and I
really believe it's an illusion anyway. The correct response is to deal
with the human problem that people are afraid of bad pads, not to attempt
to somehow get rid of bad pads. Or else, sacrifice perfect secrecy. We
have such good crypto nowadays (unless you believe in David Scott's
all-powerful NSA computers that can break 128-bit symmetric crypto in
milliseconds) that we shouldn't need OTPs. People who are doing
professional espionage and believe that they really do need OTPs, can (I
hope) be counted on to *be* professionals, and understand that the bad pad
"problem" is an illusion.
--
Matthew Skala
[EMAIL PROTECTED] "I fish stranger things than you
http://www.islandnet.com/~mskala/ out of my granola every morning."
------------------------------
From: "Cristiano" <[EMAIL PROTECTED]>
Subject: Re: DL blind signature
Date: Thu, 3 May 2001 19:51:26 +0200
Thank you for have answered to my old message.
"David Hopwood" wrote:
> Cristiano wrote:
> > In many systems (or perhaps in all) for the blind signature based on DL,
> > one must choose a prime q that divides p-1 (also p is prime) and then a
> > generator in the moltiplicative group Zq*
>
> That sounds wrong. Are you sure you're not confusing it with "a generator
> of a subgroup of order q in Z*_p"? That is what Chaum-Pederson works in.
You are right! But could you explain me the practical difference?
> > (cfr Chaum-Pedersen from paper "Loyalty Program Scheme
> > for Anonymous Payment Systems" by Arrianto Mukti Wibowo and Kwok Yan
Lam).
> >
> > Doing some trials with small numbers, when I compute the public key
y=g^a
> > mod p (a is my private key) for all a<p, the distribution of y may be
very
> > bad; on the contrary, if I compute y=g^a mod q for all a<q, the
distribution
> > is as expected: I get all the elements in Zq* (g is a generator!).
> > Why this "strange" set up?
> >
> > My implementation of the algorithm in the above paper at page 13
> > (Chaum-Pedersen blind signature) doesn't work. The modulo for all the
> > calculations is not shown. Is it always mod p or mod q?
>
> Generally in discrete-log-based protocols (including Chaum-Pederson),
[...]
Thank you very much for the explanation! Now I have understood!
Cristiano
------------------------------
From: "Cristiano" <[EMAIL PROTECTED]>
Subject: Re: Message mapping in EC.
Date: Thu, 3 May 2001 19:42:47 +0200
"Nobody" wrote
> Cristiano wrote:
> > "Mike Rosing" wrote:
> <snip>?
> Is it good that m>p map on the curve?
>
> Yes. The operation of multiplication is this:
>
> mult(a, fx)
> a = a << 1;
> if(MostSigBit(a) == 1)
> a = a ^ fx; // this removes the MostSigBit, forcing all values <fx
> return a;
> end
I use GF(p) and I saw that if m>p miracl library (I use this) do m=m mod p.
I think that this is bad because the message changes!
Is there any way to fix the problem?
Cristiano
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: A Question Regarding Backdoors
Date: Thu, 03 May 2001 18:12:14 GMT
"Rick Wash" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> "Tom St Denis" <[EMAIL PROTECTED]> writes:
>
> > "Tim Smith" <[EMAIL PROTECTED]> wrote in message
> > news:[EMAIL PROTECTED]...
> > > On Mon, 30 Apr 2001 11:11:33 GMT, Tom St Denis <[EMAIL PROTECTED]>
> > > wrote:
> > > > Then he should ask the right question which is "Is it legal to
> > > > use > 256-bit symmetric keys in the US". This has nothing todo
> > > > with AES or possible
> > >
> > > That's not the right question. The right question is whether he
> > > has to put a backdoor into his system, which is what he asked. No
> > > one else seems to be having trouble understanding the question, so
> > > the problem is you, not him.
> >
> > To me that's the last thing a serious cryptographer should be
> > asking. Most have problems enough with inadvertant bugs that
> > cripple systems (PGP, Netscape, etc...) let alone intentional bugs
> > or faults.
>
>
> No, it is not. At the very least, the US government has made some
> very serious proposals for backdoors into cryptosystems. For example,
> look at the proposed Key Escrow systems. One of the drawbacks of
> these systems is that they only work if everyone plays by the rules,
> and to get everyone to play by the rules the government will have to
> outlaw non-backdoored crypto. If a serious cryptographer plans to
> continue being a serious cryptographer, then he/she should be careful
> to obey the law and not end up in jail.
>
> I personally don't like the idea of having backdoors in my crypto
> software, whether intentional or not, but when I write the software I
> am careful to check and make sure that I will not end up in jail for
> it. It is a very important question, and a good thing that he asked.
> Better safe than sorry in a case like this.
The problem with crypto laws
a) Written by brain-dead idiots
b) Usually don't matter
c) Goto a.
If you restrict the use of legitimate crypto what says criminals would
follow the law? Also the purpose of limitting crypto is not to ensure the
safety of law abiding people it's to catch criminals (just incase anyone
wants to bring gun laws in here that's not the point.
Personally within the US afaik there are no restrictions. If you want
international crypto move to Canada or europe or something.
Tom
------------------------------
From: Doug Kuhlman <[EMAIL PROTECTED]>
Subject: Re: Message mapping in EC.
Date: Thu, 03 May 2001 13:11:10 -0500
Mike Rosing wrote:
>
> Cristiano wrote:
<SNIP>
> > You need 5 bits to make sure data will fit on the curve, so that
> > leaves plenty for raw data.
> >
> > Is this only an aproximate measure or does it have some explanation?
>
> It's empirical observation. A company wanted to make sure their registration
> system would work, and I suggested that 4 bits was enough. So they ran a test,
> and in 10 million tries they found 5 errors. So we went with 5 bits. After 60
> million tries there were no errors, i.e. all data was recovered since it fit
> on the curve.
>
Seems like they were lucky (and/or more is going on than meets the
eye). We expect approximately 1/2 of the x values to be on the curve
(semi-rigorously, due to Hasse-Weil). With 4 "play" bits, you would get
16 possible x-values. A priori, we would expect to see about 153 (10
million / 2^16) "misses".
With five bits, you get 32 possible values for x, which means about 1 in
4 trillion values is expected (with no other thought) to "miss" being on
the curve.
I am, of course, assuming that the position of the "play" bits is fixed,
so that there is no ambiguity on the receiver's end. Allowing for more
movement of these bits increases the chances of success but seems to
needlessly complicate the system.
> The explanation has to do with the density of points. For any x value, there
> is some radius measured in hamming weight which will find an x value which is
> on the curve. I am not sure any mathematician has looked at the problem as it
> would be a rather hard one to prove. Empirical proof works in the real world,
> so I'll accept it :-)
>
I am quite sure many mathematicians *have* looked at it. And, yes, it
is quite difficult to prove in practice -- at least as difficult as
results about densities of primes. There are lots of factors that go
into trying to rigorously prove that a point exists in every Hamming
sphere of radius n.
I do accept the empirical *evidence* that it works, though. There is
also some sound mathematical reasoning why it should. Proof is a ways
away, though.
Doug
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Ciphertext only
Date: Thu, 03 May 2001 12:46:13 -0600
Jeffrey Williams wrote:
<snip>
> Bottom line, in the most general case derived from your question, the
> answers are "No" and "No".
<snip>
I'd say "it depends" and "it depends".
The "most general case" has to include, for example, some
ciphertext from rot-13, even if you expect pgp more often.
JM
------------------------------
From: "Cristiano" <[EMAIL PROTECTED]>
Subject: Re: Message mapping in EC.
Date: Thu, 3 May 2001 21:10:30 +0200
"Mike Rosing" wrote:
> Cristiano wrote:
> >
> > I use the curve 160 r1 from "SEC 2: Recommended Elliptic Curve Domain
> > Parameters", p is a 160 bit number (2^160-2^31-1).
> > If I start with m=84894A24.... (these are the firsts 32 bits of 160) it
> > doesn't map until m=6 84894A24... (163 bits). Is it good that m>p map on
the
> > curve?
>
> In principle it doesn't matter. [...]
This is still true if the library (I use miracl) does m=m mod p.
I think that this is bad because the message changes!
Thanks
Cristiano
------------------------------
From: Jeffrey Williams <[EMAIL PROTECTED]>
Subject: Re: Ciphertext only
Date: Thu, 03 May 2001 15:46:04 -0500
I guess it depends, pun partially intended, on what we mean by "general
case". I take it to mean the situation in which you have cipher text and
no other information whatsoever. In that case, the most reasonable
expectation is that you will not be able to decipher the cipher text.
There will be specific cases where Joe Bonehead used something useless like
ROT13 and if you care to test for specific cases such as that, you can
indeed break them. However, the general rule will be that you will not be
able to decipher the cipher text. Hence, my answers.
Mostly, our disagreement is on semantics. If you like, tack on a proviso,
"provided the creator of the cipher text didn't use something totally
trivial like ROT13", to my answer.
Jeff
John Myre wrote:
> Jeffrey Williams wrote:
> <snip>
> > Bottom line, in the most general case derived from your question, the
> > answers are "No" and "No".
> <snip>
>
> I'd say "it depends" and "it depends".
>
> The "most general case" has to include, for example, some
> ciphertext from rot-13, even if you expect pgp more often.
>
> JM
------------------------------
From: "Paradigm" <[EMAIL PROTECTED]>
Subject: How much math is required to study this?
Date: Thu, 3 May 2001 22:49:04 +0200
Hi,
I'm finishing high school this year and I will apply for university right
after to study math and computer science.
I'm very interested in cryptography but I don't know very much about it. In
high school, we've learned about how RSA works but only from a math
perspective, not from a cryptography perspective.
I would really like to study cryptography, from the most simple ciphers to
the most complex. My aim is to become so good that I can figure out ways to
attack ciphers or possibly even design my own (I'm very impressed when I see
postings here where some clever people are able to, apparently without too
much difficulty, find loopholes in proposed ciphers etc.
Anyway, I'm wondering if you could recommend some good books that doesn't
require too much math. I took the 3-year A-level course in high school (In
Denmark we've A, B and C level courses in high school) which among other
things includes integration calculus, vectorials (is that what it's called
in English?) and elementary number theory (not analytical). I've read a book
on analytical number theory on my own.
Will this be enough for studying cryptography on my own or will I have to
wait to we learn more math at uni?
I really hope there is a good book on the subject that is advanced at the
same time as being understandable to a person at "my level".
I apologize for spelling errors etc. (I'm not a native speaker!)
Thank you in advance,
Martin
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Random and not random
Date: Thu, 03 May 2001 22:50:45 +0200
Matthew Skala wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> >infinite source. So suppose one employs a statistical
> >test to discard some segments of the sequence output from
> >the source. We can first consider that these segments are
> >employed to encrypt some dummy (unimportant) messages and
> >one actually sends them together with the proper messages
> >that are encrypted with the remaining segments of OTP that
>
> It's not good enough for an OTP to be randomly generated. It must be
> randomly generated *and* independent of the plaintext. If it's not, then
> you lose perfect secrecy. If you send different plaintexts, or the same
> plaintexts in a different order, depending on the results of statistical
> tests on the pad, then your plaintext and pad are not independent, and you
> lose the perfect secrecy property. You'll probably need some way of
> communicating which pads were discarded or used for dummy messages, but
> we'll ignore that; I don't think that's a difficult problem to solve.
>
> If you do use the bad pads for dummy messages instead of discarding
> them, then you still have a bad pad problem. Suppose I generate a bad pad
> segment that just happens to be equal to my secret message XORed with the
> dummy message I was going to use. That will probably fail the statistical
> tests (XOR of two plaintexts tends to still have low
> statistically-measured entropy) so I will use it for my dummy message...
> and end up transmitting my secret message unencrypted!
>
> It gets worse. Suppose my pad, XOR whatever I'm going to XOR it with,
> happens to correctly predict the secret message that I'm going to want to
> transmit some time next week. At this point, I don't even *know* that
> it's a bad pad... but if I use it, I will be transmitting, unencrypted, a
> secret that I will want to keep from my enemy.
>
> Suppose I'm so frightened of bad pads that I don't transmit any messages
> at all. I just encrypt them and throw them away. But my enemy is running
> a random pad generator too and it just by random chance happens to
> generate my stream of plaintext! Now my friends don't get the message
> because I was so afraid that I didn't send it, but the enemy *does* get
> the message! Oh, horror! What can we do about this?
>
> I really don't think there is any way around the bad pad "problem", and I
> really believe it's an illusion anyway. The correct response is to deal
> with the human problem that people are afraid of bad pads, not to attempt
> to somehow get rid of bad pads. Or else, sacrifice perfect secrecy. We
> have such good crypto nowadays (unless you believe in David Scott's
> all-powerful NSA computers that can break 128-bit symmetric crypto in
> milliseconds) that we shouldn't need OTPs. People who are doing
> professional espionage and believe that they really do need OTPs, can (I
> hope) be counted on to *be* professionals, and understand that the bad pad
> "problem" is an illusion.
Let me repeat my arguments in a different way. Suppose
I have a perfect OTP source and I have n messages, which
for simplicity may be assumedd to be of the same length.
I encrypt these via xor with n segments of the OTP. Am I
sure that the opponent can't decrypt any of them? If no,
why? Suppose the answer is yes. Now, up till here nothing
has been said about what I may or may not put into these
massages, i.e. I may write a top secret, or I may write
something that is totally commonplace, yet all are
perfectly secure in the sense that the opponent can't
know what I have actually put in the messages? Am I
right? If not, why? Suppose the answer is yes. Now, as
sender I know the contents of the messages (the opponent
doesn't before succeeding in cracking them). Suppose
there are two types of messages as said above, type A
the top secrets, type B the trivialities. Suppose
there are n1 of the first and n2 of the second kind. Now
I test the OTP segments with a certain statistical test.
Again, for convenience of arguments, suppose that there
'happen' to be n1 segments that pass the test and n2
segments that fail that. I choose to encrypt the n1 type
A messages with the n1 segments that pass my test and
the the n2 type B messages with the remaining n2
segments. Is this o.k. or not? If not why? (Does the
original OTP processing scheme say anything about
whether I am forbidden to encrypt with any given segement
any arbitrarily given messages?) Suppose the answer
is yes. Now let's see what the opponent has in his
hand. He has got n = n1 + n2 messages in encrypted form.
None of the messages can he crack according to the
theory of OTP. That is, neither the n1 nor the n2
ciphertexts can he decrypt. In particular, he can't
crack the n1 messages in their ciphertext form. Is
that right? If no, why? If yes, then consider the
situation where the n2 messages are not sent in the
first place. In this case, the total amount of items
that the opponent has to work on is certainly reduced
from n to n1. But since, as said above, he can't
crack not even a single one of the n1 ciphertexts,
he doesn't have any advantage in now being able to
concentrate his resources (from dealing originally
n ciphertexts) on the n1 ciphertexts. This, however,
would mean that my original claim is correct, isn't
it?
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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
