Cryptography-Digest Digest #171, Volume #12 Thu, 6 Jul 00 20:13:00 EDT
Contents:
Re: Beginner Questions (Bob Silverman)
Re: Crypto jokes? (potentially OT) ("Paul Pires")
Re: Data compression and encryption ("Douglas A. Gwyn")
Re: cray and time needed to attack ("Douglas A. Gwyn")
Re: A simple all-or-nothing transform (Mark Wooding)
A new cipher........ (Simon Johnson)
Re: Prime Numbers? ("Douglas A. Gwyn")
Re: Any crypto jokes? (potentially OT) ("Paul Pires")
Re: A thought on OTPs (Mok-Kong Shen)
Re: Crypto jokes? (potentially OT) (David A Molnar)
Re: Has RSADSI Lost their mind? ("Trevor L. Jackson, III")
Re: cray and time needed to attack ("Joseph Ashwood")
Re: RPK (David Hopwood)
Re: RPK (Simon Johnson)
Re: A new cipher........ ("Joseph Ashwood")
Re: Crypto jokes? (potentially OT) (Allan Crossman)
Re: Crypto jokes? (potentially OT) ("Paul Pires")
Re: Encryption and IBM's 12 teraflop MPC...... (Dan Day)
Re: Any crypto jokes? (potentially OT) ("Trevor L. Jackson, III")
Re: Any crypto jokes? (potentially OT) (Dan Day)
Re: Any crypto jokes? (potentially OT) ("Trevor L. Jackson, III")
Re: Crypto jokes? (potentially OT) ("Trevor L. Jackson, III")
----------------------------------------------------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: Beginner Questions
Date: Thu, 06 Jul 2000 18:49:12 GMT
In article <8k2f0t$25o$[EMAIL PROTECTED]>,
"AC" <[EMAIL PROTECTED]> wrote:
>
> Excuse my ignorance but cryptography is only a hobby for me.
>
> A couple of posts talk about 1024 bit prime numbers. Do these numbers
=
> have 128 digits (1024/8)?
No.
Hint: if a number has 1024 bits it is between 2^1023 and 2^1024-1.
Think about why you divide by 8.
>
> Also, what is the most efficient, time wise, to handle 100+ digit =
> numbers in C++? I have set up an array to hold each digit of a number
> but this seems cumbersome and is terribly slow.
Use a radix bigger than 10. Use (say) 2^30
Now each number is represented as:
a0 + a1 * 2^30 + a2 * 2^60 + ....
Now store each a_i in a word of an array. This is much more
efficient than storing just 1 digit.
Read chapter 4 of Knuth Vol. 2. [This is ESSENTIAL reading]
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: Crypto jokes? (potentially OT)
Date: Thu, 6 Jul 2000 12:10:38 -0700
<[EMAIL PROTECTED]> wrote in message news:8k1r9e$qhl$[EMAIL PROTECTED]...
> Does anyone know any crypto-related jokes or links to them?
> Or perhaps someone could come up with an ingenious answer to the
> question:
>
> How may cryptographer does it take to change a light bulb?
One, but you can't *PROVE*
that it has been changed.
>
> Thanks in advance for any suggestions
>
> rot26
>
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
>
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Data compression and encryption
Date: Thu, 6 Jul 2000 18:24:48 GMT
Dido Sevilla wrote:
> Do all cryptologic transformations modify the information content
> of a message, e.g. make a message compress better or worse than
> the unencrypted message for some given compression algorithm?
That depends on the details. The general principle, however, is
that the ciphertext contains information from the key as well as
*all* the original plaintext information, so the ciphertext must
have more entropy than the plaintext, so in general terms it is
less compressible.
> If so, then by how much?
No worse than by the amount of information in the encryption key.
However, the redunancy is usually is a much less accessible form
in the ciphertext than in the plaintext, so general-purpose
compression algorithms cannot exploit the redundancy and thus do
a lousy job of compression.
> It seems that at the very least, the one-time pad would serve
> to increase the information content of a message such that it
> would be nearly impossible to compress by any means after
> encryption, provided the OTP was properly produced.
In fact the information content of the ciphertext in the context
of the interceptor's knowledge is exactly that of a uniform
random bit (or character, or whatever) string of length equal
to that of the key (which is equal to the message length).
Such a "random" string can be compressed sometimes, but the
expected *average* performance of any predetermined (reversible)
compression algorithm for such strings is actually expansion.
> Since the security of the OTP is what all cryptosystems aspire to,
> am I correct in asserting that all encryption systems must increase
> the information content of any message by an amount proportional to
> the size of the key used?
I don't follow your logic -- what does it matter what cryptosystem
designers "aspire to"?
A simple counterexample is a system that (unwittingly or not)
doesn't use every bit in the key. (Or, more practically, for
which it is possible for different keys to map some given
plaintext to the same ciphertext.)
> Therefore, if any data compression is to be performed on data to
> be encrypted, it should be done *before* any encryption.
Um, yes, I thought that was well understood. It's not just
because of the reduction in the ciphertext length yielding
better use of available bandwidth, but also because there is
less redundancy in the ciphertext for the cryptanalyst to
exploit. Also, compressing the ciphertext with some fixed
scheme offers no additional security, since the attacker can
readily uncompress the ciphertext before analysis.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: cray and time needed to attack
Date: Thu, 6 Jul 2000 18:31:18 GMT
Mike Rosing wrote:
> I would say supercomputers are on the desktop now.
Supercomputers evolve, too, so whatever is the current desktop computer
is certainly not the current supercomputer.
It is truly depressing to think that the horrible PC architecture
(both ISA and I/O) is getting more and more deeply entrenched as
time goes on, not to mention Windows.
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: A simple all-or-nothing transform
Date: 6 Jul 2000 19:16:57 GMT
David Hopwood <[EMAIL PROTECTED]> wrote:
> (Frankly, I don't see the point of the scheme in Rivest's 1997 paper;
AONTs are useful in conjunction with chaffing and winnowing: you can
drastically reduce the amount of chaff you need to create if the
adversary must pick out exactly which packages are wheat before he can
decode.
-- [mdw]
------------------------------
Subject: A new cipher........
From: Simon Johnson <[EMAIL PROTECTED]>
Date: Thu, 06 Jul 2000 12:35:38 -0700
Right, this is my first 'real' cipher i've posted here.
Its a 64-bit block cipher with a 128-bit key. There is no source
available yet (sorry, i havn't had the time), and i've done it
for a friend (I took D.A. Wagner's advice, and had a proper go!)
I doubt its secure, because i don't know how to analyse these
things properly. It intended as a learning experience.....
The PDF file can be found at:
http://dimension.h3o.org/~pabalo/JC1.pdf
Any comments, analysis?
===========================================================
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Prime Numbers?
Date: Thu, 6 Jul 2000 18:44:33 GMT
[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: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: Any crypto jokes? (potentially OT)
Date: Thu, 6 Jul 2000 12:45:54 -0700
I like it.
Isn't that WOM memory.
AKA, Write Only Memory
Paul
Larry Kilgallen <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> In article <8k1ol9$p2k$[EMAIL PROTECTED]>, [EMAIL PROTECTED] writes:
> > Does any body know any crypto-related jokes,
>
> I have found a way to use One-Time-Pads by generating the
> pads at both ends during operation.
>
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: A thought on OTPs
Date: Thu, 06 Jul 2000 22:05:35 +0200
"Douglas A. Gwyn" wrote:
> Mok-Kong Shen wrote:
> > Also I asked sometime back whether there are good tests for
> > independence in practice but failed to get a concrete answer.
>
> I think you got answers, but just didn't like them.
> "Independence" of events is a theoretical notion used in models.
> It is not directly testable, but its consequences are testable
> with the usual statistical tools of hypothesis testing.
If these 'consequences' that you mean (I am not aware, please name
these) could not be related mathematically to what I want to test,
namely independence, then they are of no use to me for my enquiry,
isn't it?
M. K. Shen
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Crypto jokes? (potentially OT)
Date: 6 Jul 2000 19:57:45 GMT
Paul Pires <[EMAIL PROTECTED]> wrote:
>> How may cryptographer does it take to change a light bulb?
> One, but you can't *PROVE* that it has been changed.
>>
uh, or rather, you *can* prove that it's been changed, but only as
the number of cryptographers and the number of lightbulbs involved
approaches infinity...and subject to some assumptions about the color of
rock in the centre of Mt. Everest...and only for very oddly shaped
lightbulbs...
It's not crypto-related in the sense this newsgroup usually tends towards,
but the 1999 New Security Paradigms Workshop has a humorous play which
compares various techniques for software assurance to different kinds of
garages. The halpless protagonist bounces from one to the other,
desperately trying to get his brakes fixed...he starts out in the Formal
Methods Garage. "Transition to Greeting State, Customer Unit!"
-David
------------------------------
Date: Thu, 06 Jul 2000 16:22:51 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Has RSADSI Lost their mind?
Eric Lee Green wrote:
> [EMAIL PROTECTED] wrote:
> >
> > Below is a couple of messages posted to the OpenSSL users mailing list.
> > Seems someone down at RSADSI has lost it.
>
> No, this is typical behavior for RSADSI. They have a habit of sending out
> threatening BS letters at the slightest provocation, such as when they
> recently threatened to sue a Canadian citizen for violating the patent on the
> RSA public key encryption algorithm.
I think they were complaining about RC5, a symmetric cipher, rather than their
asymmetric cipher.
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: cray and time needed to attack
Date: Thu, 6 Jul 2000 13:53:39 -0700
> It is truly depressing to think that the horrible PC architecture
> (both ISA and I/O) is getting more and more deeply entrenched as
> time goes on, not to mention Windows.
I find it depressing also, but ISA is all but dead, with various vendors
offering "legacy-free" computers, it should soon disappear entirely (in
favor of PCI, which is vastly superior but also has problems), also old-form
PC I/O is disappearing in favor of USB. So the technology is evolving, but
there're still those old 8086 instructions that I wish they'd get rid of.
Joe
------------------------------
Date: Thu, 06 Jul 2000 20:23:16 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: RPK
=====BEGIN PGP SIGNED MESSAGE=====
[EMAIL PROTECTED] wrote:
> In article <[EMAIL PROTECTED]>,
> tomstd <[EMAIL PROTECTED]> wrote:
> > why do you suggest [RPK] is suited for music?
>
> My answer seems to have been lost, so I will try again to reply to you.
> Based on what the authors say, its main advantage is to work very well
> with a connectionless protocol like UDP, you can miss bits of your
> message and be able to decode the rest.
You can also do that with any other hybrid cryptosystem that uses a
stream cipher for the symmetric part. However, don't do it without being
aware of the implications for active attacks that change the stream.
- --
David Hopwood <[EMAIL PROTECTED]>
PGP public key: http://www.users.zetnet.co.uk/hopwood/public.asc
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOWTcijkCAxeYt5gVAQFVkAf/Xm0ZW53FRmYR0PYVRX2xRSntSgW/61BV
UyEgAds/BhY/MqFoYRUR0cAl0i04T8qO4FtLYb4GOKYlLLYCHoJZUpIbntDxeHpr
j7BhIa/SGBDc+skVeRX5jWBLC4+w0JSVwODnh6kRD81Dqr4lZZrl/t6c7kYdsgYQ
got2zh2MEeBoLGoH33sLeB5bNPQkaxVeuFPLDTxN2SUdocvsYe+gQn/e4eXjte1c
eBKHEIKGbmuBAveAWzODKuy+GVGd29SknWMs7BbJwYVhAt7gieTRi+Dg7nCq8lCN
czIifZcFU5e8c4icKhgDalfCM/IBk+6r8IJkg1i9M19Sx80msdJcfg==
=Ldgh
=====END PGP SIGNATURE=====
------------------------------
Subject: Re: RPK
From: Simon Johnson <[EMAIL PROTECTED]>
Date: Thu, 06 Jul 2000 14:29:28 -0700
>why do you suggest it is suited for music?
>
>Tom
I could see it being useful for music web-broadcasting. So that
you don't get Mallory putting Nazi properganda into the radio
stream. ;) But other than that, it seems a little pointless.
===========================================================
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: A new cipher........
Date: Thu, 6 Jul 2000 14:41:24 -0700
While I haven't finished reading the paper yet, I did notice that in your
round function there is a very large amount of interdependence, this could
be a bad thing because it means that if an attacker can guess one value a
large amount of information about the other values is leaked. I also noticed
(I'm not sure if it's an error, or what you intended) that Q2 is not updated
in the second batch of equations, leaving is as S3((A2 + B2) mod 256) this
poses a risk versus the other equations as the value of Q2 is more closely
linked A and B than the others. And one thing that I'm sure is an error in
the second set of equations, Q3 depends on Q4, which is undefined until
afterwards.
Joe
"Simon Johnson" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Right, this is my first 'real' cipher i've posted here.
> Its a 64-bit block cipher with a 128-bit key. There is no source
> available yet (sorry, i havn't had the time), and i've done it
> for a friend (I took D.A. Wagner's advice, and had a proper go!)
>
> I doubt its secure, because i don't know how to analyse these
> things properly. It intended as a learning experience.....
>
> The PDF file can be found at:
> http://dimension.h3o.org/~pabalo/JC1.pdf
>
> Any comments, analysis?
>
>
> -----------------------------------------------------------
>
> Got questions? Get answers over the phone at Keen.com.
> Up to 100 minutes free!
> http://www.keen.com
>
------------------------------
From: [EMAIL PROTECTED] (Allan Crossman)
Subject: Re: Crypto jokes? (potentially OT)
Date: Thu, 06 Jul 2000 23:56:34 +0100
In article <8k2obp$rki$[EMAIL PROTECTED]>, David A Molnar
<[EMAIL PROTECTED]> wrote:
> Paul Pires <[EMAIL PROTECTED]> wrote:
> >> How may cryptographer does it take to change a light bulb?
>
> > One, but you can't *PROVE* that it has been changed.
> >>
>
> uh, or rather, you *can* prove that it's been changed, but only as
> the number of cryptographers and the number of lightbulbs involved
> approaches infinity...and subject to some assumptions about the color of
> rock in the centre of Mt. Everest...and only for very oddly shaped
> lightbulbs...
Or rather, only one, but if you ask him to prove he changed it, he'll
probably make a hash of the whole thing.
Allan Crossman (do a rot-13 on hxbayvar)
http://www.faldara.co.uk
==================================================
PGP Keys: 0x68367A23 (DH/DSS) and 0xFC31CE1F (RSA)
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: Crypto jokes? (potentially OT)
Date: Thu, 6 Jul 2000 16:13:25 -0700
Allan Crossman <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> In article <8k2obp$rki$[EMAIL PROTECTED]>, David A Molnar
> <[EMAIL PROTECTED]> wrote:
>
> > Paul Pires <[EMAIL PROTECTED]> wrote:
> > >> How may cryptographer does it take to change a light bulb?
> >
> > > One, but you can't *PROVE* that it has been changed.
> > >>
> >
> > uh, or rather, you *can* prove that it's been changed, but only as
> > the number of cryptographers and the number of lightbulbs involved
> > approaches infinity...and subject to some assumptions about the color of
> > rock in the centre of Mt. Everest...and only for very oddly shaped
> > lightbulbs...
>
> Or rather, only one, but if you ask him to prove he changed it, he'll
> probably make a hash of the whole thing.
You asked for it.
None, one tried but he snagged his IV and pre-whitened himself.
Paul
------------------------------
From: [EMAIL PROTECTED] (Dan Day)
Subject: Re: Encryption and IBM's 12 teraflop MPC......
Date: Thu, 06 Jul 2000 23:23:53 GMT
On Wed, 5 Jul 2000 21:51:14 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
>> So no, a computer that's 12,000 times faster than the
>> fastest new PC on the market doesn't make a really big dent.
>> Unless, of course, you know a good breakthrough shortcut
>> algorithm... But a shortcut, if any exists, is just
>> as likely to be feasible on a 166MhZ Pentium as it is
>> to require the kind of horsepower a 12 teraflop computer
>> gives you.
>
>There is a big difference between knowing what the message
>says sometime next year and knowing today.
I'm aware of that. That's why I made a point of
mentioning that a hypothetical breakthrough may well be of
a type where a 12 teraflop computer isn't any better or
worse, in a practical sense, than a 166MhZ Pentium.
Perhaps I wasn't clear enough. Here's what I meant...
There are three possibilities when it comes to the
situation I was describing:
1. There's a moderate breakthrough, and it buys many orders
of magnitude over available methods, but it
still takes billions of years to crack
a modern-sized key even with the new 12 teraflop computer.
2. There's a big breakthrough, and it happens to be such
that a 12 teraflop computer can crack keys in
a practical amount of time (say, less than a week)
but a Pentium computer cannot.
3. There's an enormous breakthrough, and using it even
a lowly Pentium computer can crack keys in seconds.
For cases #1 and #3, the existence of a 12 teraflop computer
doesn't make any difference either way when it comes to
cryptographic cracking.
It's only case #2 where a computer a thousand or so times
faster than existing computers will make any real difference.
And my point is that this "in between" situation is a very
narrow band, comprising only a very few orders of magnitude
of difficulty out of hundreds -- a breakthrough is less likely
to fall right on that range of possibility than it is to fall into
category #1, or category #3.
--
"How strangely will the Tools of a Tyrant pervert the
plain Meaning of Words!"
--Samuel Adams (1722-1803), letter to John Pitts, January 21, 1776
------------------------------
Date: Thu, 06 Jul 2000 19:48:42 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Any crypto jokes? (potentially OT)
Joseph Ashwood wrote:
> <[EMAIL PROTECTED]> wrote in message news:8k1ol9$p2k$[EMAIL PROTECTED]...
> > Does any body know any crypto-related jokes, or have links to websites
> > that contain them?
> Does Szopa count? Oops, sorry I don't know him, forget I said anything.
The fact that we think so and he thinks not, counts.
------------------------------
From: [EMAIL PROTECTED] (Dan Day)
Subject: Re: Any crypto jokes? (potentially OT)
Date: Thu, 06 Jul 2000 23:53:30 GMT
On Thu, 06 Jul 2000 10:56:43 GMT, [EMAIL PROTECTED] wrote:
>Does any body know any crypto-related jokes, or have links to websites
>that contain them?
http://www.ii.uib.no/~larsr/craptology/crv0n1-2.html
This is a, um, paper entitled "Practical Key Recovery",
which proposes to dramatically reduce the amount of time
necessary for automated key recovery by the ingenious
expedient of automating the torture of subjects in order
to get them to spill their keys.
--
"How strangely will the Tools of a Tyrant pervert the
plain Meaning of Words!"
--Samuel Adams (1722-1803), letter to John Pitts, January 21, 1776
------------------------------
Date: Thu, 06 Jul 2000 20:08:10 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Any crypto jokes? (potentially OT)
[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.
------------------------------
Date: Thu, 06 Jul 2000 20:14:41 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Crypto jokes? (potentially OT)
Paul Pires wrote:
> <[EMAIL PROTECTED]> wrote in message news:8k1r9e$qhl$[EMAIL PROTECTED]...
> > Does anyone know any crypto-related jokes or links to them?
> > Or perhaps someone could come up with an ingenious answer to the
> > question:
> >
> > How may cryptographer does it take to change a light bulb?
>
> One, but you can't *PROVE*
>
> that it has been changed.
Hmmm.
Light bulbs emit thermal radiation, so they are a form of RNG. If we could
find the light bulb equivalent of a PRNG we could then prove, by the lack of
entropy of the output, that the bulb had been changed for one with a different
pseudo. A laser might serve as such a non-thermal emitter.
------------------------------
** 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
******************************
