Cryptography-Digest Digest #172, Volume #12 Fri, 7 Jul 00 02:13:00 EDT
Contents:
Re: Some dumb questions (John Savard)
Re: Any crypto jokes? (potentially OT) ("Paul Pires")
Re: Quantum Computing (Was: Newbie question about factoring) (TIEMANN BRUCE)
Re: Prime Numbers? (TIEMANN BRUCE)
Re: Prime Numbers? (David Lancashire)
Re: A thought on OTPs (Joe Nilaad)
Re: Compression & Encryption in FISHYLAND (Kurt Shoens)
Re: Hash and Entropy (Benjamin Goldberg)
Re: Prime Numbers? (Nicol So)
Re: Hash and Entropy (JPeschel)
Re: Any crypto jokes? (potentially OT) (Guy Macon)
Porting Keys Between PGP, other Apps ("Ed Suominen")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Some dumb questions
Date: Fri, 07 Jul 2000 00:21:15 GMT
On Thu, 06 Jul 2000 17:40:00 +0200, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote, in part:
>Under which chapter/section of your webpage is the material
>about SIGCUM? (Sorry that I did only a quick search.)
It's at
http://home.ecn.ab.ca/~jsavard/crypto/te0305.htm
The original version had 13 live wires into five rotors, with five
wires out giving the bits to XOR with a teleprinter character.
But the improved version had five live wires in, and the wires going
out were wired together from three rotor contacts, so the chance of a
bit being a one changed to 48.846%. Thus, getting rid of correlations
must have been considered as much more important than a little bias.
John Savard (teneerf <-)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: Any crypto jokes? (potentially OT)
Date: Thu, 6 Jul 2000 17:49:32 -0700
I am truly impressed with the volume and rational appearance of this post.
Does your day job require hip waders too?
Paul
.
Trevor L. Jackson, III <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> [EMAIL PROTECTED] wrote:
>
> > How many cryptographers does it take to change a light bulb?
>
> Changing the light bulb is too hard (there can only be one AES, so we'll
never
> change anything).
>
> Turning on the light is about the right speed. One needs to attempt every
> possible set of combinations of electrical switches, including the fuse
box,
> in order to determine which set of subsets of possible combinations enable
the
> light. This technique fails in the presence of acoustic switches and BSR
X-10
> modules.
>
> Acoustic switches turn on the light and keep it on for a predetermined
period
> following the last significant sound. Controlling the lights in the
presence
> of acoustic switches requires an analysis of the sensitivity settings of
the
> switches. Thus each switch must be individually exhaustively exercised to
> determine the required volume level at each activation frequency. This
> requires a form of differential spectral analysis which is beyond the
scope of
> this joke.
>
> BSR X-10 modules permit remote control of the light. Since the switches
are
> typically controlled by a computer (or close facsimile) finding all of the
> possible controls that enable the light is equivalent to the halting
problem
> for the computer. So deciding how to turn on the light is undecidable.
> Actually turning on the light requires even more effort. In this
situation
> the author respectfully suggests candles.
>
>
------------------------------
From: [EMAIL PROTECTED] (TIEMANN BRUCE)
Crossposted-To: comp.theory
Subject: Re: Quantum Computing (Was: Newbie question about factoring)
Date: 7 Jul 2000 01:06:09 GMT
In article <[EMAIL PROTECTED]>,
Paul E. Black <[EMAIL PROTECTED]> wrote:
>Nick Maclaren wrote:
>> However, some people believe that building a quantum computer is
>> an exponentially complex problem,
>
>Interesting. Could you give more details, for instance, who believes
>that or what goes into it? For instance, is it that designing a
>quantum computer is exponentially complicated, or constructing it
>(an exponential number of steps needed)?
>
>-paul-
>--
>Paul E. Black ([EMAIL PROTECTED])
I have heard that quantum computers require as many bits in the readout of
some analog state as qbits in the data; thus, readout of a quantum state
to the nearest percent provides ~6-7 bits accuracy. Reading out that
state to ppm-level accuracy would provide 20 qbits. By the way, ppm-level
accuracy - not precision, accuracy - is extremely difficult, and would
afford only 20 bits, hardly enough to get excited about. Digging for the
next sigfig in the readout of some analog data is exponentially harder
than was the last one.
This may have some bearing to the problem.
------------------------------
From: [EMAIL PROTECTED] (TIEMANN BRUCE)
Subject: Re: Prime Numbers?
Date: 7 Jul 2000 01:11:41 GMT
In article <8k2g60$8le$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
>I understand the distinction now, thank you. I had read an explanation
>of Euclid's proof in an article in Scientifc American july 1988 p. 120,
>it goes like this: (it's in the form of a dialogue between 2 people who
>pan for primes on the bank of the Continuum river)
>...
>TYRO: Hey mister! How far downstream do the primes go?
>YUKE: Why, boy, all the way to the Sea of Infinity.
>TYRO: I don't believe you. Here we are at the millions and I haven't
>seen color all day.
>YUKE: You tenderfeet have to be told everything. Look, suppose you
>came to the largest prime. No more after that, right?
>TYRO: Uh, right.
>YUKE: Call it n. You take and form the product of all primes there are
>right up to n. Ok? That's 2x3x5x...xn. Now add 1 to the product and
>call the number you finally get p.
>TYRO: Don't tell me that p is a prime!
>YUKE: Sure is. Prime as all get-out. Look, you can't divide it by 2
>because there's 1 left over, you can't divide it by 3 because there's 1
>left over. There's always 1 left over, right up to n. There's just no
>getting around it.
>TYRO: Gosh, I guess that's what keeps you going.
>...
>
>So the article is misleading when it says that this p will always be a
>prime?
It will either be a new prime, or it will be composite with all factors
greater than n, hence, not on the list. In either case, you will expand
your *known* list of primes.
------------------------------
From: David Lancashire <[EMAIL PROTECTED]>
Subject: Re: Prime Numbers?
Date: Thu, 06 Jul 2000 21:30:44 -0400
Ahh... of course. Apologies for any confusion caused by my last post,
and thanks to all for the swift correction.
best,
--david
Douglas A. Gwyn wrote:
> [EMAIL PROTECTED] wrote:
> > So the article is misleading when it says that this p
> > will always be a prime?
>
> Not just misleading, but wrong. Suppose you thought 13
> was the greatest prime: 2*3*5*7*11*13+1 = 30031 = 59*509.
> For 17 it's 19*97*277. For 19 it's 347*27953. We're not
> having much luck, are we? But note that in every case the
> smallest prime factor is bigger than our assumed biggest
> prime. That's the correct deduction, which contradicts
> the assumption, proving the converse: reductio ad absurdum.
------------------------------
From: Joe Nilaad <[EMAIL PROTECTED]>
Subject: Re: A thought on OTPs
Date: Thu, 06 Jul 2000 19:12:53 -0700
"Douglas A. Gwyn" wrote:
> [snip]
> Other, less trivial examples are also possible. Here is just one:
> C[i] = P[i] + K[i]^2 mod m, where m is the size of the alphabet.
> With this cipher, for a given C[i] only a proper subset of characters
> are possible for P[i], which of course is less than perfectly secure.
> So it isn't just *using* uniform key at the same rate as PT, but *how*
> the key is used.
What do you mean by "...,for a given C[i] only a proper subset of
characters are possible for P[i]"? It seems to me that if m is 8 bits
in size, then there are 256 characters are possible for each C[i].
Whether or not the decrypted messages are readable, that is another
story.
If I encrypt a message "AAAA" with a key [K1] that yields cipher
"$%^&" and send to Tony Warnock, you intercept the cipher "$%^&"
and decrypt it with a key [K2] which yields plantext "BBBB", then
how would you know for sure that "BBBB" is what I sent to Tony?
The same cipher, "$%^&", can easily yield "CCCC", "DDDD",
"I AM", etc., with a particular matched key.
Your scheme will work fine with simple X-OR.
OTP is secure due to the key will not be reused, or do I miss something?
Joseph K. Nilaad
------------------------------
From: [EMAIL PROTECTED] (Kurt Shoens)
Subject: Re: Compression & Encryption in FISHYLAND
Date: 6 Jul 2000 19:59:40 -0700
In article <[EMAIL PROTECTED]>, Tim Tyler <[EMAIL PROTECTED]> wrote:
>To think that inadequate key management is the *only* case where the
>ability to rapidly reject bad keys helps does not appear to be correct.
>
>Consider the case where the attacker has a known-plaintext attack on the
>algorithm. Here, sections of the key may be revealed even if the
>management of the key has otherwise been excellent.
I'm speaking in the context of current algorithms considered to be
secure. Such algorithms are expected to be immune to chosen plaintext
attacks. If having a fixed block of zeros encrypted were useful, a
chosen plaintext attack could have that information. In fact, encryption
algorithms are faulted even if too many rounds of a reduced-round variant
are susceptible.
Sure, if you choose an algorithm susceptible to known plaintext
attacks, then 1-1 compression may help. But why make that choice
with so many sound alternatives available?
>If it takes frequency analysis on a significant volume of the message
>to spot a correct plaintext, then that's obviously going to be slower
>than (say) the case of looking for a header of all-zeros in the first block.
I am willing to stipulate that 1-1 compression will require decrypting
the entire file to check a key in a brute force attack. For example,
with 16-byte blocks, the work factor for a 1 megabyte file would be
increased by 2^16. Alternatively, with apparently little or no cost,
you could choose 256-bit keys rather than 128-bit keys in AES.
In any event, why worry about it? Brute force attacks on 128-bit keys
aren't feasible on single blocks anyway.
To put it more plainly, 1-1 compression makes an already infeasible
attack slower, so it accomplishes nothing.
>"Bad key management" reduces the search space. It doesn't affect whether
>the search is looking for something it knows how to recognise. You can
>still have some pretty good encryption with a key-space of only 2^8 keys.
I can't see how 8-bit keys will be satisfactory, but in any event, who
cares? We can have symmetric key sizes as large as we need and far
beyond the reach of brute force attacks.
>*If* you were arguing that the 1-1 property is icing on the cake of
>compression - and that compression is icing on the cake of encryption
>(from a security POV) - then I might agree with you.
The 1-1 property does nothing for me in compression. In compression,
I want something that has the right combination of compression
effectiveness and speed for the data at hand. From an encryption
algorithm, I want security independent of the plaintext.
>This material is mainly of significance because cryptographers try to
>live close to the edge, and produce the best systems they know how to -
>because competition means that if they don't, then other folks will.
I interpret this to mean that cryptographers try to design the fastest
algorithms with acceptable security. The security/speed tradeoff has
significant in the AES competition, but even their, not all entrants
viewed it the same way. Compare Serpent and Rijndael, for example.
While presenting the advantages of 1-1 compression, you've indicated
its value in the context of bad choices, such as a presenting an
attacker with a small search space of keys or choosing a poor encryption
algorithm. Security is better served by avoiding the poor choices.
As a postscript: if one pursues this work for the academic interest of
it, that's wonderful. My reading of the original poster indicates
interests that are pragmatic rather than academic.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Hash and Entropy
Date: Fri, 07 Jul 2000 03:30:15 GMT
Mark Wooding wrote:
>
> Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
>
> > I thought that a "random oracle" was an oracle that had a way of
> > getting Truly Random bits from somewhere in a single step.
[Your defn of "random oracle" snipped]
> A `random oracle' will compute a function chosen randomly and
> uniformly from \Omega. It will always use the same function, but it
> won't tell you what the function is. Both the `good guys' and the
> adversary are given access to the oracle.
Sounds like you're using "random oracle" to mean some kind of black-box?
[snip]
> You could possibly think of the oracle as something which:
>
> * given an input it's not seen before, responds with a string of
> random data; and
>
> * given an input it has seen before, response with the same string
> it responded with last time.
Hmm, now this kinda sounds like you're describing something entirely
different... Are you giving two different definitions, or what?
--
This is the signature retro-virus.
Help me spread by copying me over your signature virus.
------------------------------
From: Nicol So <[EMAIL PROTECTED]>
Subject: Re: Prime Numbers?
Date: Thu, 06 Jul 2000 23:30:29 -0400
Reply-To: see.signature
"Douglas A. Gwyn" wrote:
>
> [EMAIL PROTECTED] wrote:
> > So the article is misleading when it says that this p
> > will always be a prime?
>
> Not just misleading, but wrong. Suppose you thought 13
> was the greatest prime: 2*3*5*7*11*13+1 = 30031 = 59*509.
> For 17 it's 19*97*277. For 19 it's 347*27953. We're not
> having much luck, are we? But note that in every case the
> smallest prime factor is bigger than our assumed biggest
> prime. That's the correct deduction, which contradicts
> the assumption, proving the converse: reductio ad absurdum.
I wouldn't call the the article misleading or wrong, but one does have
to be careful when understanding what it says.
In a proof by contradiction (reductio ad absurdum), *a* false conclusion
is derived from a set of premises. In a valid argument, the conclusion
is always true if all the premises are true. If the conclusion is false,
then at least one of the premises must be false. Generally speaking,
there are many possible false conclusions you can derive from such a set
of premises using a valid argument, depending on the argument used.
In the case of Euclid's proof (as illustrated in the Scientific American
article), "p is a prime" is *a* (false) conclusion derivable from the
(false) premises using a valid argument. It would be true *if* the
assumption were. The last point is what the proof is trying to
illustrate.
--
Nicol So, CISSP // paranoid 'at' engineer 'dot' com
Disclaimer: Views expressed here are casual comments and should
not be relied upon as the basis for decisions of consequence.
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: Hash and Entropy
Date: 07 Jul 2000 04:21:26 GMT
[EMAIL PROTECTED] (wtshaw) writes:
>In article <[EMAIL PROTECTED]>,
>[EMAIL PROTECTED] (JPeschel) wrote:
>
>> [EMAIL PROTECTED] (wtshaw) wrires, in part:
>>
>> >The biggest problem is that the word can be taken to be opposite in
>> >meaning, such as "raising" a structure means.... to build it, or tear it
>> >down.
>>
>> Nope, raising and razing are two different words.
>>
>> >...which means that other words are better used, or that improper use is
>> >simply based on a poor understanding of physics.
>>
>> or a poor understanding of English.
>
>I know that they are two different words, but chose to bait the hook.
>It's the sound thing like emmigrate and immigrate. In spoken context,
>relying on minor spelling differences are inadequate. That was really my
>point, mispelled on purpose, that something is a whole, or a hole,
>depending on what you think of it.
Bait the hook? Nah, you gave a poor example.
You orginally wrote:
"The biggest problem is that the word can
be taken to be opposite in meaning, such
as "raising" a structure means.... to build
it, or tear it down. Entropy is taken as a
measure of order and of disorder in science,
which means that other words are better used,
or that improper use is simply based on a
poor understanding of physics."
If you meant two different words that sound alike
say so: "raising" and "razing" -- two different words.
Even then, however, "raising" versus "razing" is a poor
example of what you mean. Apparently, in your example
you want two words that sound alike, but have opposite
meanings. "Emmigrate" and "immigrate" rhyme two
syllables, but they certainly don't sound the same,
nor do "entropy" and "intropy."
"Whole" and "hole" sound alike, but aren't quite
opposites.
I suppose you could try the word "bad," which means
bad, and, when I was a kid, anyway, meant good, too.
Then there's "cool" which means just about anything
you like, although Gwyn wryly suggests it's synonym for
stupid.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: Any crypto jokes? (potentially OT)
Date: 07 Jul 2000 01:39:20 EDT
Paul Pires wrote:
>
>
>I like it.
>
>Isn't that WOM memory.
>
>AKA, Write Only Memory
>
Right. I keep them next to my inoperational amplifiers, never gates,
dark emitting diodes, electrolytic confetti generators, and the ever
popular single shot acoustic noise emiting diode with memeory (SSANEDWM).
------------------------------
From: "Ed Suominen" <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp,comp.security.pgp
Subject: Porting Keys Between PGP, other Apps
Date: Thu, 6 Jul 2000 23:01:03 -0700
Can you port an RSA private/public key pair between PGP and other
applications? I have been experimenting with Adobe Acrobat 4.0's signature
handler and have gotten it to create a PKCS #7 certificate of my
experimental RSA key. (Thanks for explaining what PKCS is.) Then I
successfully imported the Base-64 text of the certificate into PGPKeys.
However, I obviously couldn't get my private key for signing since the
certificate is something you send around to people. Also, there was some
discrepancy between how the "Digital ID" app. and PGPkeys treated the public
key. See below.
Try importing the PKCS certificate text and the public key into PGPkeys and
you'll get the same key in your public keyring.
Can anyone shed light on this and why the PKCS #7 "thumbprint" is different
from the PGP "fingerprint" when its the same exact RSA key?
--
Ed Suominen
Registered Patent Agent
Web Site: http://eepatents.com
PGP Public Key: http://eepatents.com/key
RSA 1024 bit public key:
3081 8902 8181 00A3 F955 096E AA52 BEE5 92F6 D494 3138 4FE4 DC2E 81EE 51DE
A485 8A7B 7B39 8C9B A8D4 0AF6 5BFF 5CAC C67D 5380 2B5A A53A 9C95 F63D CA3F
E9BB 93C1 0AB9 7F67 08E2 A838 27B9 D29C 743D BEE3 FF17 D083 9FE1 610D 246B
3A07 E5BB BCF8 E953 5DFB 5D3D 0024 F239 90D6 5AE5 243B 7B97 5ED7 8E34 9D16
2EEC 3488 52A2 5C79 CA36 84F9 CE55 1902 0301 0001
#1. "Digital ID" application, opening Base64 X.509 Public Key Certificate:
=====BEGIN CERTIFICATE=====
MIIByTCCATKgAwIBAgIEA5AF3jANBgkqhkiG9w0BAQQFADApMQswCQYDVQQGEwJV
UzEaMBgGA1UEAxMRRWR3aW4gQS4gU3VvbWluZW4wHhcNMDAwNzA1MDgwOTUxWhcN
MDUwNzA1MDgwOTUxWjApMQswCQYDVQQGEwJVUzEaMBgGA1UEAxMRRWR3aW4gQS4g
U3VvbWluZW4wgZ8wDQYJKoZIhvcNAQEBBQADgY0AMIGJAoGBAKP5VQluqlK+5ZL2
1JQxOE/k3C6B7lHepIWKe3s5jJuo1Ar2W/9crMZ9U4ArWqU6nJX2Pco/6buTwQq5
f2cI4qg4J7nSnHQ9vuP/F9CDn+FhDSRrOgflu7z46VNd+109ACTyOZDWWuUkO3uX
XteONJ0WLuw0iFKiXHnKNoT5zlUZAgMBAAEwDQYJKoZIhvcNAQEEBQADgYEAVJo4
tr73HJhnnEoCIKYNYlxK2tnwDcjV2y+c3jUot8Yn+meeLY+u+ffb2t+xvyzm3TIr
mLp/m0AVkvTzwSY5IXgQbJz/96CKdZRKbDl3hxOgGTe/AriJQK8sRArIgciq/BMO
a2VYZn1kpuLYkuCeIDJk/7ykazc8kCyYvsv89vI=
=====END CERTIFICATE=====
SHA1 "Thumbprint"
91FE 6BC5 A1F8 6B0A 4B19 A035 B36B 136E 4C47 1944
S/N 0390 05DE
#2. After importing the "CERTIFICATE" block above into PGPKeys, then
exporting to ASCII:
=====BEGIN PGP PUBLIC KEY BLOCK=====
Version: PGP Personal Privacy 6.5.3
mQCPAzli7U8AAAEEAKP5VQluqlK+5ZL21JQxOE/k3C6B7lHepIWKe3s5jJuo1Ar2
W/9crMZ9U4ArWqU6nJX2Pco/6buTwQq5f2cI4qg4J7nSnHQ9vuP/F9CDn+FhDSRr
Ogflu7z46VNd+109ACTyOZDWWuUkO3uXXteONJ0WLuw0iFKiXHnKNoT5zlUZABEB
AAG0GkNOPUVkd2luIEEuIFN1b21pbmVuLCBDPVVTiQHsBBBkAQHfBQI5Yu1PBQMJ
Z1MAwRFkAQEEMIIByTCCATKgAwIBAgIEA5AF3jANBgkqhkiG9w0BAQQFADApMQsw
CQYDVQQGEwJVUzEaMBgGA1UEAxMRRWR3aW4gQS4gU3VvbWluZW4wHhcNMDAwNzA1
MDgwOTUxWhcNMDUwNzA1MDgwOTUxWjApMQswCQYDVQQGEwJVUzEaMBgGA1UEAxMR
RWR3aW4gQS4gU3VvbWluZW4wgZ8wDQYJKoZIhvcNAQEBBQADgY0AMIGJAoGBAKP5
VQluqlK+5ZL21JQxOE/k3C6B7lHepIWKe3s5jJuo1Ar2W/9crMZ9U4ArWqU6nJX2
Pco/6buTwQq5f2cI4qg4J7nSnHQ9vuP/F9CDn+FhDSRrOgflu7z46VNd+109ACTy
OZDWWuUkO3uXXteONJ0WLuw0iFKiXHnKNoT5zlUZAgMBAAEwDQYJKoZIhvcNAQEE
BQADgYEAVJo4tr73HJhnnEoCIKYNYlxK2tnwDcjV2y+c3jUot8Yn+meeLY+u+ffb
2t+xvyzm3TIrmLp/m0AVkvTzwSY5IXgQbJz/96CKdZRKbDl3hxOgGTe/AriJQK8s
RArIgciq/BMOa2VYZn1kpuLYkuCeIDJk/7ykazc8kCyYvsv89vIAAAAAAAEB
=xfXP
=====END PGP PUBLIC KEY BLOCK=====
PGP "Fingerprint"
8EBF A10B A170 376D BCB6 649D 6143 D34A
Cipher IDEA, KeyID 0xF9CE5519
------------------------------
** 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
******************************
