Cryptography-Digest Digest #780, Volume #10 Tue, 21 Dec 99 20:13:01 EST
Contents:
Re: Q: transcendental pad crypto (John Savard)
Re: How do you know if you found a key? (John Savard)
elliptical curve encryption (MANIK TANEJA)
Re: Keystrokes monitored/encryption useless (Liyang Hu)
Re: RSA, how to calculate big numbers (Ian Goldberg)
Re: How do you know if you found a key? (Ian Goldberg)
Re: Q: transcendental pad crypto (Gregory G Rose)
Re: QPK (Ian Goldberg)
Re: DES as pseudo random number generator (Scott Nelson)
Re: --- sci.crypt charter: read before you post (weekly notice) (N. Mayoliker)
Re: Implementing ElGamal (Pelle Evensen)
Of one time pads, plaintext attacks, and fantasy ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Q: transcendental pad crypto
Date: Tue, 21 Dec 1999 15:45:18 GMT
Tim Tyler <[EMAIL PROTECTED]> wrote, in part:
>John Savard <[EMAIL PROTECTED]> wrote:
>
>: But the one-time-pad is awkwards enough so that algorithms are used
>: for encryption - but the algorithm of calulating the decimal expansion
>: of a mathematical formula is not a particularly good one for this
>: purpose.
>
>It would be a terrible one if "real" randomness was being sought - but
>it's not one that is implied by the term "transcendental number".
>
>It is true that "PI" and "e" are well known transcendental numbers - but
>it's *not* part of the definition of a transcendental number that its
>digits can be generated by some finite formula.
I addressed that in a post in another branch of this thread:
'Well, I'm assuming that one can't, say, evaluate a physical voltage
level to 1000 digits.
Thus, I'm expecting that you mean a transcendental number like
"sqrt(pi+e)" ... and the complexity of the expression for it is the
originating key length.'
John Savard (jsavard<at>ecn<dot>ab<dot>ca)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: How do you know if you found a key?
Date: Tue, 21 Dec 1999 15:46:54 GMT
Greg <[EMAIL PROTECTED]> wrote, in part:
>Assume that it is just random and means nothing. Really.
>This is the case I am asking about. Can you know when you
>found the key that produces that specific random data
>if you do not know what it is you should see?
Then there is no danger of decryption.
John Savard (jsavard<at>ecn<dot>ab<dot>ca)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: MANIK TANEJA <[EMAIL PROTECTED]>
Subject: elliptical curve encryption
Date: Wed, 22 Dec 1999 04:24:02 +0000
hi all ! can someone provide me with a reference to details, algorithms,
implementation issues on ECES. thank you
Regards
Manik Taneja
[EMAIL PROTECTED]
------------------------------
From: Liyang Hu <[EMAIL PROTECTED]>
Subject: Re: Keystrokes monitored/encryption useless
Date: Tue, 21 Dec 1999 21:58:01 -0000
At Tue, 21 Dec 1999 11:41:54 -0600, Medical Electronics Lab
<[EMAIL PROTECTED]> said:
> Liyang Hu wrote:
> > Assuming the person cannot reach your machine physically. I'm talking
> > about software security here, not things like surveillance or tempest
> > attacks. Slight problem with your attack is that I'd notice it straight
> > away, with my PC sitting in the middle of my bedroom...
> > I had contenplated building a keyboard sniffer before, with a PIC16C84,
> > saving the keystrokes to an external eeprom. (well, you're plugging that
> > damn STAMP shite ;) I nearly got most of the design done, but luckily for
> > our school's system admin, I never got around to making it, due to lack of
> > time...
>
> Sounds like a fun project. Instead of saving the data, you could
> broadcast it. Digikey and Jameco sell some nice (small) transmitters
> and receivers. This would be a good school project because you'd
> get to learn a lot of stuff and you'd also scare the hell out of
> any teacher with sense enough to check their own keyboard :-)
Frankly, I'm sick of projects involving PIC's, or any other
microcontroller for that matter. Every issue of every damn electronics
magazine now has at *least* one project involving one of those. I wish for
the old days when electronics required years of experience to get to grips
with, and when you could see from the circuit diagram how a certain
project worked. Now it's all just programming.
Anyway, I doubt I'd learn anything new from this.
Apart from that, I dont have much spare time now for electronics anyway,
especially seeing as I'm not taking Technology for my A-Levels. Although I
have to agree with you - it would have been fun, if I had built it :)
--
��,����`Liyang Hu/DenseBoy����,��,����http://www.nerv.cx/`����,��
| The subspace W inherits the other 8 properties of V. |
| And there aren't even any property taxes. |
| -- J. MacKay, Mathematics 134b |
------------------------------
From: [EMAIL PROTECTED] (Ian Goldberg)
Subject: Re: RSA, how to calculate big numbers
Date: 21 Dec 1999 23:14:03 GMT
In article <[EMAIL PROTECTED]>,
Ian Wehrman <[EMAIL PROTECTED]> wrote:
>get on a unix machine, use 'bc'
You meant 'dc':
$ echo '32567023914 367151 40000399997 |p' | dc
726580
- Ian
>Bart Peeters wrote:
>>
>> I have to calculate:
>>
>> (32567023914^367151)%40000399997
>>
>> How can I do that?
------------------------------
From: [EMAIL PROTECTED] (Ian Goldberg)
Subject: Re: How do you know if you found a key?
Date: 21 Dec 1999 23:39:31 GMT
In article <83osoe$dhu$[EMAIL PROTECTED]>, Greg <[EMAIL PROTECTED]> wrote:
>What I am wondering (to cut to the chase) is how is it that
>using DES three times is not as strong as triple DES? My
>understanding is that triple DES encrypts, then decrypts then
>encrypts again, rather than encrypting three levels deep, and
>that the reason is that it is stronger that way.
No, it's not the fact that the middle op is a decrypt rather than an
encrypt that makes 3DES stronger than DES x 3. Changing the definition
of 3DES to use 3 encryptions in a row doesn't (to anyone's knowledge)
weaken its strength.
However, it also depends what you mean by "using DES three times".
Let's say I've got a long message, and a program that encrypts using
DES, say in CBC mode (the choice of CBC is just an example, here). I
run that program three times, with three independently-chosen keys,
using the output of one iteration as the input to the next.
If the program puts some kind of checksum or other redundancy on the
message, in order to tell you if the decryption is valid, or if it puts
known headers on the *output* (which are then fed into the next
iteration as input), then clearly this only requires 3*2^55 work to
break.
Suppose we're cleverer, and the program simply derives a key and IV from
the passphrase, and encrypts the data using DES-CBC (which won't change
its size, assuming the input was a multiple of 8 bytes). Then it would
seem we're in the case you describe, where any attempts to decrypt would
just show you the (random-looking) output of the previous encryption.
This is in fact how most *hardware* implementations of 3DES work, and
it's called "inner-chaining" mode. It's popular in hardware, because it
turns out you can easily use 3 DES chips in parallel to get a pipelined
3DES encryption with the same bulk speed as single DES.
Turns out we're not so clever. Or, more precisely, Biham is more
clever. I refer you to J. Crypto 12/3: Cryptanalysis of Triple Modes of
Operation, E. Biham, Pages 161-184, in which he outsmarts whole classes
of inner-chaining modes such as this one.
In contrast, the way most *software* implementations of 3DES work is
called "outer-chaining" mode. As opposed to inner chaining, where the
whole message is processed by DES, then that whole result is processed
by DES again, etc., with outer chaining, the blocks are taken one at a
time, and each one is processed by 3 DES's before outputting it and
moving on to the next one.
It turns out that, to our knowledge, this is much stronger.
So, in the sense of "encrypt a whole message at a time", using a 3DES
program is stronger than using a DES program 3 times.
- Ian
------------------------------
From: [EMAIL PROTECTED] (Gregory G Rose)
Subject: Re: Q: transcendental pad crypto
Date: 21 Dec 1999 15:54:12 -0800
In article <83ojjk$6eb$[EMAIL PROTECTED]>, Bob Silverman <[EMAIL PROTECTED]> wrote:
>Let me try to put an end to this nonsense before it goes any further.
>
>(1) There are very few numbers in mathematics that are actually KNOWN
>to be transcendental. One can indeed construct infinitely many
>transcendentals based on Liouville's theorem or from Thue's theorem.
>But such numbers are USELESS for cryptographic purposes: they have
>predicatable digit patterns and they are NOT normal numbers.
Wow, that rarest of occurrences: a chance to tell
Bob he should have done more research. :-)
There is a paper by Josef Pieprzyk and others
about using transcendental numbers for stream
ciphers. A quick altavista doesn't find
it. (Ha! Google presents me with a cached copy of
a page that I "don't have permission to access":
J. Pieprzyk, H. Ghodosi, C. Charnes, R.
Safavi-Naini, Cryptography based on
transcendental numbers, Information Security and
Privacy, J. Pieprzyk and J. Seberry (Eds),
Lecture Notes in Computer Science, Vol.1172,
Proceedings, First Australasian Conference on
Information Security and Privacy, ACISP'96,
Wollongong, Australia, June 24-26, 1996, Springer
1996, pp.96-107
)
Anyway, from memory now, any algebraic number
raised to an algebraic power is transcendental. As
far as the authors were concerned, the numbers
were of cryptographic quality. So, for example,
you could use sqrt(2)**sqrt(5). However, as usual,
this is totally impractical, and anyway,
effectively the key becomes the two numbers (2, 5)
which still gives a limited search space.
I agree with Bob's conclusion, which I paraphrase
as "give up now".
Greg.
--
Greg Rose INTERNET: [EMAIL PROTECTED]
QUALCOMM Australia VOICE: +61-2-9181 4851 FAX: +61-2-9181 5470
Suite 410, Birkenhead Point http://people.qualcomm.com/ggr/
Drummoyne NSW 2047 B5 DF 66 95 89 68 1F C8 EF 29 FA 27 F2 2A 94 8F
------------------------------
From: [EMAIL PROTECTED] (Ian Goldberg)
Subject: Re: QPK
Date: 21 Dec 1999 23:55:18 GMT
In article <[EMAIL PROTECTED]>,
Medical Electronics Lab <[EMAIL PROTECTED]> wrote:
>Mok-Kong Shen wrote:
>> But I do like to know what is your definition of 'probabilistic
>> encryption'. Do you mean a process where at some step a decision
>> is made depending on the output of a (deterministic) pseudo-random
>> generator or else on a truly random event which even the legitimate
>> receiver of the encrypted message can't know/predict? The first
>> case would only be an application of PRNG (I used it in one of my
>> schemes), while in the second case the receiver has no easier job
>> than the analyst, or do I miss something?
>
>You encrypt with something that does not have a unique inverse.
>If you know the key, there may be 4 or 8 "decryptions". By checking
>all of them, you can figure out which is the correct one by some
>other item in the data. The recipient does not know which one
>is right a priori, they have to check them all.
>
>In this case, you add 2 or 3 bits to the the analyst's task over
>finding the key. For the receiver, checking 8 possible decryptions
>is trivial.
Hmm. I don't think that's the _usual_ definition of "probabilistic
encryption". What you describe is more like the differential workfactor
stuff used in, for example, the export version of Lotus Notes. The
sniffer needs to try 2^64 keys to break the message, but the "intended"
recipient (the NSA) is told 24 of them, so they only need to try 2^40
keys (easy!). :-)
What I usually call "probabilistic encryption" is where the space C of
ciphertexts is partitioned into a number of subsets, each corresponding
to an element of the space P of plaintexts. This partitioning and
corresponding is key-dependent, of course. The output of an encryption
of a given plaintext is a *random* element of the subset of C which
corresponds to that plaintext. So _encryption_ of a message can take on
a large number of values. In contrast, _decryption_ is unique; given
any element of C, it is in exactly one of the partitions, which
corresponds to exactly one element of P.
This notion is most commonly used in public-key cryptography, where
*anyone* can calculate the encryption function. Without it, for example,
decrypting a message which is known to be either "yes" or "no" would be
trivial; just encrypt both of those messages, and see which matches.
With probabilistic encryption, there are too many possibilities for the
encryption to try them all.
The simplest way to do probabilistic encryption is just to pad the
message with some randomness before encrypting it. Exactly how you do
this, though, is algorithm-dependent, and, it turns out, subtle.
>Another idea is something like a "k out of n scheme", which uses
>multiple dimensions to allow many key holders to have some information
>about a key, but it takes at least k of them to figure out all the
>equations to find the key. If you have k-1, you can do a search over a
>vastly reduced key space, which is kind of like probalistic encryption.
Why is the keyspace vastly reduced? In a (good) k-of-n scheme,
each share has as much entropy as the key itself, and knowing k-1 of the
shares gives you exactly 0 information about the key, so guessing that
last share is as hard as guessing the whole key from scratch.
- Ian
------------------------------
From: [EMAIL PROTECTED] (Scott Nelson)
Subject: Re: DES as pseudo random number generator
Reply-To: [EMAIL PROTECTED]
Date: Wed, 22 Dec 1999 00:24:35 GMT
On Tue, 21 Dec 1999 "Trevor Jackson, III" <[EMAIL PROTECTED]> wrote:
>Eric Lee Green wrote:
>
>> "Trevor Jackson, III" wrote:
>> > > you wish to use DES as your PRNG, key DES from your random input and then run
>> > > DES in CFB/counter mode. This will give you a cycle time of 2**64, but that's
>> > > still better than most PRNG's.
>> >
>> > You are overstating your case here. 64 bits is small for most reasonable PRNGs.
>> > Marsaglia's PRNG library consists of a bunch of one-line PRNGs and I believe they
>are
>> > all much larger than 64 bits..
>>
>> I think you are, in turn, overstating YOUR case. "reasonable" PRNGs are still
>> a rarity. I have examined the source for the rand() function that's in the
>> FreeBSD and Linux "C" libraries, for example, and it has a 2^31 cycle time
>> (not to mention only 2^32 initial states!). Similarly, the "whrand()" library
>> included with Python has 2^24 initial states, and a cycle time of 2^45.
>
>Sampling error. Nobody serious uses a C-compiler's rand() function. That's a
>classical
>error that goes back 3-4 decades.
Yes, and people still love the classics.
Lot's of people use rand(), even though it
often leads them into serious trouble.
But the trouble with rand() is that it's an LCG,
not that it's 64 bit. For example, the DJGPP
rand() uses a LCG with a 64 bit size, and returns
bits 25-57. It "fails" several of the
Diehard tests.
Marsaglia's COMBO generator on the other hand,
( http://www.helsbreth.org/random/rng_combo.html )
is only about 60 bits, but passes all of them.
Neither would provide adequate security for
a pseudo one time pad, but then, DES in
counter mode wouldn't either.
Scott Nelson <[EMAIL PROTECTED]>
------------------------------
From: [EMAIL PROTECTED] (N. Mayoliker)
Crossposted-To: talk.politics.crypto
Subject: Re: --- sci.crypt charter: read before you post (weekly notice)
Date: Wed, 22 Dec 1999 00:29:40 GMT
chuck davis <[EMAIL PROTECTED]> wrote:
>There's no gimmicks with the code, no commercial tie-ins, just an honest
>challenge. Is there somewhere I can tell code-crackers everywhere about this
>thing?
Why don't you try alt.brain.teasers? If you want to offer a challenge to
sci.crypt, then give a complete description of your encryption algorithm,
along with source code, and challenge them to find a method of recovering
the plaintext without the key. To challenge cryptography enthusiasts to
make sense of gibberish is pointless and boring.
I don't think people here are angry about the message you posted, they're
angry about all of the messages here that you never bothered to read.
--
"N. Mayoliker" is actually [EMAIL PROTECTED] (1678 023549).
0 123456789 <- Use this key to decode my email address and name.
Play Five by Five Poker at http://www.5X5poker.com.
------------------------------
From: Pelle Evensen <[EMAIL PROTECTED]>
Subject: Re: Implementing ElGamal
Date: Wed, 22 Dec 1999 01:37:18 +0100
Rowland Smith wrote:
> Are there any good references on the web concerning the ElGamal algorithm?
Try Handbook of Applied Cryptography, chapter 8.
http://www.cacr.math.uwaterloo.ca/hac/about/chap8.pdf
/Pell
------------------------------
From: [EMAIL PROTECTED]
Subject: Of one time pads, plaintext attacks, and fantasy
Date: Wed, 22 Dec 1999 00:51:35 GMT
Towards the end of "Cryptonomicon" by Stephenson (interesting
novel by the way, anybody know of any others that use crypto as a plot
device??) there's a part in which one of the "heroes" describes
how he broke a very complex system that was essentially a one-time pad
(as I understand the term). The major breakthrough came when he planted
some info and then waited for it to appear in an intercept.
I know that in general, that was a technique sometimes used during
wartime to break enemy ciphers. But the more I thought about it, I don't
see how that would work with a one-time system.
The system in question was based on generating a pseudo-random sequence
(using a Riemann-zeta function) and then adding it mod(26) to the
plaintext.
In the text, he speaks of looking for the word CROCODILE, GOLD, FUNERAL
and a few others.
Here's my confusion:
Given that it is a random sequence of additives, how could you tell if a
given sequence of ciphertext tranlated back to a given plaintext? And
suppose it did, since its a contantly changing sequence, the particular
additive that worked for say the first "C" in crocodile wouldn't be the
same for the second.
Am I missing something here? Or was this just one of those convient
flights of fancy that make for a good story...if not a technically
accurate one?
=====
PS: As I was typing this message, an idea come to me that I suppose
might work.....
1) Starting at the beginning of the ciphertext (or wherever) determine
what sequence is neccesary to convert the character sequence to the
suspected plaintext.
2) work backwards and figure out the input seed to the zeta function
required to produce the additive sequence found in step one.
3) Apply the output of the function to the entire ciphertext and see if
any sort of sensible plaintext results.
if not then...
4) step forward one character in ciphetext and start over.
Sounds REALLY tedious!!
Any ideas?
=====
"ignoti et quasi occulti"
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
** 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
******************************
