Cryptography-Digest Digest #686, Volume #12 Fri, 15 Sep 00 12:13:00 EDT
Contents:
Re: 20 suggestions for cryptographic algorithm designers ("Trevor L. Jackson, III")
Diffie-Hellman Questions (Future Beacon)
Re: 20 suggestions for cryptographic algorithm designers ("Trevor L. Jackson, III")
Re: 20 suggestions for cryptographic algorithm designers (Mathew Hendry)
Re: Intel's 1.13 MHZ chip ("Trevor L. Jackson, III")
Re: Extremely slow in DES software implementation ("Kasper Pedersen")
Re: 20 suggestions for cryptographic algorithm designers (Paul Schlyter)
Re: Intel's 1.13 MHZ chip (Mok-Kong Shen)
Re: Fresh Meat: New Crypto Algorithms Announced (Mok-Kong Shen)
Re: Diffie-Hellman Questions (Doug Stell)
Re: GSM tracking (Jerry Coffin)
Re: Intel's 1.13 MHZ chip (Jerry Coffin)
----------------------------------------------------------------------------
Date: Fri, 15 Sep 2000 10:17:25 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: 20 suggestions for cryptographic algorithm designers
John Savard wrote:
> On Fri, 15 Sep 2000 00:24:13 -0400, "Douglas A. Gwyn"
> <[EMAIL PROTECTED]> wrote, in part:
> >David Hopwood wrote:
> >> IMHO the arguments for big-endian order are more compelling.
>
> >Unfortunately, some of the ones you gave were bogus.
> >Both camps can arrange "compelling" arguments for their choice.
> >I prefer little-endian representation for multiple-precision
> >applications because it is slightly more efficient on average.
> >It seldom matters enough to argue about.
>
> Inside a processor, it indeed doesn't matter. Big-endian has
> advantages for compare instructions, and little-endian has advantages
> for arithmetic.
>
> But when attempting to describe a block cipher algorithm to human
> beings, who are used to a language whose writing system is derived
> from the Latin alphabet, and whose numeration system is based on
> Hindu-Arabic numbers, big-endian ordering has significant advantages
> in making a specification clear, understandable, and unambiguous.
I disagree. A careful description will be sufficiently precise that
endianness is not relevant to the clarity of the presentation. Only a
description that relies upon the prejudice of the reader -- always a
dangerous thing -- will be clearer and more understandable for BE order.
And any ambiguity is inexcusable. It is a flaw in the thoroughness of
the presentation rather than an incentive for a stylistic convention.
------------------------------
From: Future Beacon <[EMAIL PROTECTED]>
Subject: Diffie-Hellman Questions
Date: Fri, 15 Sep 2000 10:22:56 -0400
I have searched the Internet for explanations of the
Diffie-Hellman algorithm and the description below
is my distillation of what little I have found. Can
anybody recommend a really complete on-line source
for the algorithm? Is there any particular way that
the base and the modulus must be chosen? I assume that
they must be different primes. I would appreciate the
correction of any misconceptions revealed by the description.
Thank you for your help.
Jim Trek
Future Beacon Technology
http://eznet.net/~progress
[EMAIL PROTECTED]
==============================================================
Diffie-Hellman Encryption uses two constants, the base, Q, and
the modulus, M. Communicating parties A and B both generate secret
keys at random. Let these keys be called Sa and Sb. They also
create public keys. These public keys are computed as follows:
Pa = Q^Sa mod M
Pb = Q^Sb mod M
Seeking a procedure for generating a key that can be used in
common by A and B, we start with this observation:
Q^(Sa * Sb) mod M = Q^(Sa * Sb) mod M expression equals itself
Q^(Sb * Sa) mod M = Q^(Sa * Sb) mod M Sb*Sa = Sa*Sb
(Q^Sb mod M)^Sa mod M = (Q^Sa mod M)^Sb mod M
and substituting Pb, we have
Pb^Sa mod M = (Q^Sa mod M)^Sb mod M
and substituting Pa, we have
Pb^Sa mod 5 = Pa^Sb mod 5
The foregoing derivation need not be done by or even know to
A or B, but now we know that both A and B can arrive at a the
same key (that they can use in common) by sending each other
their public keys and finding the common key this way:
A computes Common Key = Pb^Sa mod 5.
B computes Common Key = Pa^Sb mod 5.
------------------------------
Date: Fri, 15 Sep 2000 10:31:59 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: 20 suggestions for cryptographic algorithm designers
John Savard wrote:
> On 14 Sep 2000 20:59:15 GMT, [EMAIL PROTECTED] (D. J. Bernstein) wrote, in
> part:
> >David Hopwood <[EMAIL PROTECTED]> wrote:
> >> If there is a completely arbitrary choice of byte order, use big-endian.
>
> >No. Little-endian is much more widely supported than big-endian, and is
> >universally supported by new processors.
>
> I don't want to start a religious war here, but if yoou use
> big-endian, the description of your algorithm will be easier to
> understand, and less likely to be ambiguous by accident.
>
> This is because English is written from left to right, and numbers are
> written with their most significant digits on the left. So
> illustrations of a sequence of digits being fed into a block cipher
> will be able to show the bits of a block in order - and each bit will
> be in the place, and performing the function, that a reader "expects",
> whether he interprets the binary bits as being a single binary number,
> or as a series of 8-bit bytes in order from first to last.
Since children in elementary school do not have trouble adding columns of
figures in LE order, I doubt computer professionals will have trouble
interpreting the left-to-right presentation of LE numbers.
There are really three layouts of interest: computer memory, written order, and
human memory. Human memory is not constrained to match either of the others.
It is perfectly capable of using an ordering appropriate to the task at hand:
arithmetic or comparison.
After all, the bits of a binary representation are not intrinsically ordered.
We impose that ordering when we deal with subsets of the full binary
representation. So humans should select the appropriate ordering as
necessary. And they seem to do so without problems.
------------------------------
From: Mathew Hendry <[EMAIL PROTECTED]>
Subject: Re: 20 suggestions for cryptographic algorithm designers
Date: Fri, 15 Sep 2000 15:21:00 +0100
Reply-To: [EMAIL PROTECTED]
[EMAIL PROTECTED] (John Savard) wrote:
: On Thu, 14 Sep 2000 22:19:18 -0700, Roger Schlafly
: <[EMAIL PROTECTED]> wrote, in part:
: >"D. J. Bernstein" wrote:
: >> No. Little-endian is much more widely supported than big-endian, and is
: >> universally supported by new processors.
:
: >Really? I didn't think anyone used it but the Intel Pentium and
: >DEC Alpha. Sparc, MIPS, etc are big-endian.
The MIPS processors I've used - Playstation, Playstation 2 - are
little-endian, at least in their default modes on those machines.
: But the number of people using the Sun Sparc or the MIPS
: chip - if you don't count the people using MIPS chips in video games!
Why wouldn't you count them? :) Particularly now that game consoles
are coming along with proper networking support, and are going to need
encryption. (It's already used to some extent in copy-protection).
--
Mathew Hendry, Programmer, Visual Sciences Ltd.
Work <[EMAIL PROTECTED]>, Home <[EMAIL PROTECTED]>
------------------------------
Date: Fri, 15 Sep 2000 10:38:51 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Intel's 1.13 MHZ chip
Guy Macon wrote:
> Mok-Kong Shen wrote:
>
> >To gain impressiveness is in fact often a motivation of
> >purchasing expensive exquisite things. (Ladies buy diamonds
> >for that, though artificial diamonds would look almost as
> >well.)
>
> Correction: The best imitation (not the same as artificial)
> diamonds are indistinguishable from real diamonds with the
> naked eye.
>
> >Right in the sixties one company in Munich had an
> >IBM 360/20 (its mode of operation must be ridiculous
> >for those acquanited only with today's computers) operating
> >right behind its show-window so that everybody knew that
> >it employed wonderful high-tech.
>
> Don't be silly! Nobody did such a thing - I was there and
> saw for myself. Companies put banks of tape drives and
> operator consoles behind the big windows. The actual
> computer was always put in the background.
>
> (Exception: Connection Machines and soe Crays looked cool
> enough to put up front. Not the IBM or DEC metal cabinets,
> though - too boring.)
I'm not sure it was the /20, but the models with the register displays
often caused trouble during extended floating point operations. Since
FP instruction sequences do not influence the contents of the integer
registers, the register display will appear to freeze during extended
(supercomputer-like) FP calculations.
Since this was a big enough problem to fool operators into IPLing the
machine because they thought it had crashed, imagine what effect this
would have upon an audience marveling at the speed of the machine!
------------------------------
From: "Kasper Pedersen" <[EMAIL PROTECTED]>
Subject: Re: Extremely slow in DES software implementation
Date: Fri, 15 Sep 2000 15:17:06 GMT
"P.C. Teo" <[EMAIL PROTECTED]> wrote in message
news:8psqqj$fg3$[EMAIL PROTECTED]...
> I am implementing a standard DES software (Downloaded from Internet) in my
> project. I found that it takes around 25+ seconds to encrypt a 1MB file
but
> PGP takes less than 4 seconds.
Hoping not to sound like too annoying:
I implemented DES in optimized assembler for Pentium-II/K6 and newer cpu's.
around 2.5MHz on a K7TB-700 (running 16 rounds).
Your implementation does 5000 datasets per second. It matches very closely
with the first DES implementation we wrote to verify that we'd gotten the
details right. It was written in Pascal, and operated on single bits -
booleans.
It's the only way you can get it to go that slow.
> What is the secret behind PGP. In my opinion, if we follow the DES exactly
> it will really take computer much time to go through all the step in the
Clever code. I spent 50+ hours implementing DES. That's approximately one
hour per instruction.
Good code is expensive. Excellent code is too expensive. Steal it somewhere.
It doesn't look anything like the original.
(Mine is copylefted in the same way as zlib. The source _has_ to be
available, so why not?)
/Kasper
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: 20 suggestions for cryptographic algorithm designers
Date: 15 Sep 2000 16:40:25 +0200
In article <[EMAIL PROTECTED]>,
John Savard <[EMAIL PROTECTED]> wrote:
> On Thu, 14 Sep 2000 22:19:18 -0700, Roger Schlafly
> <[EMAIL PROTECTED]> wrote, in part:
>>"D. J. Bernstein" wrote:
>>> No. Little-endian is much more widely supported than big-endian, and is
>>> universally supported by new processors.
>
>> Really? I didn't think anyone used it but the Intel Pentium and
>> DEC Alpha. Sparc, MIPS, etc are big-endian. I believe even some
>> of the Intel processors can be wired to run big or little endian.
>
> The forthcoming IA-64 or Merced will have this.
>
> However, he is correct that little-endian is more widely used. Its
> popularity derives from that of the PDP-11, which was the machine that
> the early versions of UNIX ran on. So, in the 8-bit generation, the
> 8080 and the 6502 were both little-endian, and only the 6800 was
> big-endian.
>
> The PowerPC chip supports both byte orders, although it is big-endian
> by default. But the number of people using the Sun Sparc or the MIPS
> chip - if you don't count the people using MIPS chips in video games!
> - and Mac computers - is indeed dwarfed by the people using the
> Pentium.
>
> But that is irrelevant to the "suggestions", since the rationale for
> big-endian is based on what goes on inside _people's_ heads, not
> inside computers.
Anyone who participates in the "holy war" of big-endian vs little-endian
should read Gulliver's Travel's!
There Gulliver did at one point encounter two people who were arguing
about the proper way to crack an egg. The "little endians" claimed
the egg should be cracked on the "little" end, while the "big
endians" claimed the egg should be cracked on the "big" end.
When Gulliver arrived there, these two people had been in war with
one another over several generations about this issue. Somehow
Gulliver managed to create peace between them (don't remember how -
read the book if you want to know).
And now, in our modern and supposedly enlightened society, there's
again a "war" about endian-ness.
We need a visit of a modern Gulliver!!!!!
====================================================================
IMO endian-ness doesn't matter much. I've worked with both kinds of
endian-ness and I find it easy enough to adapt. Little-endian is
slightly more machine efficient, while big-endian is slightly easier
for people to read -- but the difference is so small that it's no
point in making any fuss about it.
One way to avoid this issue completely is to return to word addressing
in computers - then this issue would become moot. You *never* hear
any discussion about the optimum "bit order within a byte": should the
byte start with the least or the most significant bit?
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pausch at saaf dot se or paul.schlyter at ausys dot se
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Intel's 1.13 MHZ chip
Date: Fri, 15 Sep 2000 17:41:21 +0200
"Trevor L. Jackson, III" wrote:
>
> Guy Macon wrote:
>
> > Mok-Kong Shen wrote:
> >
> > >To gain impressiveness is in fact often a motivation of
> > >purchasing expensive exquisite things. (Ladies buy diamonds
> > >for that, though artificial diamonds would look almost as
> > >well.)
> >
> > Correction: The best imitation (not the same as artificial)
> > diamonds are indistinguishable from real diamonds with the
> > naked eye.
> >
> > >Right in the sixties one company in Munich had an
> > >IBM 360/20 (its mode of operation must be ridiculous
> > >for those acquanited only with today's computers) operating
> > >right behind its show-window so that everybody knew that
> > >it employed wonderful high-tech.
> >
> > Don't be silly! Nobody did such a thing - I was there and
> > saw for myself. Companies put banks of tape drives and
> > operator consoles behind the big windows. The actual
> > computer was always put in the background.
> >
> > (Exception: Connection Machines and soe Crays looked cool
> > enough to put up front. Not the IBM or DEC metal cabinets,
> > though - too boring.)
>
> I'm not sure it was the /20, but the models with the register displays
> often caused trouble during extended floating point operations. Since
> FP instruction sequences do not influence the contents of the integer
> registers, the register display will appear to freeze during extended
> (supercomputer-like) FP calculations.
>
> Since this was a big enough problem to fool operators into IPLing the
> machine because they thought it had crashed, imagine what effect this
> would have upon an audience marveling at the speed of the machine!
I doubt that there are readers of this thread that had
experience with the IBM 360/20. This was at the lowest end
of the 360 series. It would be heaven and earth if one were
to compare, say, the IBM 360/91 with it. The 360/20 had an
extremely small memory. The only compilier available was an
assmbler, of course with a very limited instruction set
specific to that tiny model. One first loaded the assembler
(a deck of cards) into the machine. Then one loaded one's
program (a deck of cards) into it. The machine then punched
out a deck of cards. One loaded that deck again into the
machine to be processed by the assembler a second time. The
machine punched out again a card deck. One finally loaded
this deck into the machine (overwriting the assmebler)
and started the program run. I would be interested to
know if any readers had had comparable experiences.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Fresh Meat: New Crypto Algorithms Announced
Date: Fri, 15 Sep 2000 17:41:14 +0200
David A Molnar wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> >> Er, do they plan on *deploying* these ciphers in anything?
>
> > What could people without money do? In the worst case
> > they would die for bad nutrition.
>
> I was thinking more of reverse engineering. of course, people in a
> position to reverse engineer are unlikely to die of bad nutrition (unless
> you count an overdose of diet coca-cola).
I am sure that there were misunderstandings on both sides.
I don't think that I have properly captured what you wrote
in the last two posts. Let me on the other hand explain what
I meant. I was mockering in my first post on the fact that
they are charging fees on the algorithms. If one wants
these to be examined by as many people as possible, then
these must be offered to the public in a way as attractive
as possible. Charging money is certainly one of the worst
things for that purpose. That's why I made allusion to the
fact that there are analysts who are not rich (certainly
true to some extent) and that one could indeed achieve some
security through demanding high prices of the algorithms.
(Since those analysts who couldn't afford to pay are
excluded, the total number of analysts attacking the
algorithms is reduced, thus the chance of these being
cracked is reduced. This is also true to some extent.) I
suppose you didn't notice the :-) sign that I used in my
first post?
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Doug Stell)
Subject: Re: Diffie-Hellman Questions
Date: Fri, 15 Sep 2000 15:01:04 GMT
On Fri, 15 Sep 2000 10:22:56 -0400, Future Beacon <[EMAIL PROTECTED]>
wrote:
>I have searched the Internet for explanations of the
>Diffie-Hellman algorithm and the description below
>is my distillation of what little I have found. Can
>anybody recommend a really complete on-line source
>for the algorithm? Is there any particular way that
>the base and the modulus must be chosen? I assume that
>they must be different primes. I would appreciate the
>correction of any misconceptions revealed by the description.
The following is a handout that I use in teaching crypto, as part of
my introduction to public key techniques. It should answer your
questions and provide a worked example.
The modulus should be a large prime and p-1 should have a large prime
factor. The base should be a primative element or generator in the
field. Alternatively, it must be of sufficiently large order.
doug
Example of Diffie-Hellman, on a 4-function Calculator
=====================================================
Universal derivation
Goals: 1. Have a prime (p-1) with one large factor.
2. Know the prime factorization of (p-1).
3. Find a generator in P, knowing factorization.
Pick primes 2 and 11 as prime factorization.
p - 1 = 2 * 11 = 22, p = 23.
Generators: 5, 7, 10, 11, 14, 15, 17, 19, 20, 21
g^2 <> 1 mod 23 and g^11 <> 1 mod 23
Pick 5 as the universal generator.
---------------------------------------------------------
Alice Bob
-------------- -------------
23, 5 Universal prime & generator 23, 5
[ 21 dec, 10101 bin ] Alice's secret
14 = 5^21 mod 23 ----------> Sends to Bob 14
Bob's secret [ 10 dec, 1010 bin ]
9 Sends to Alice <---------- 9 = 5^10 mod 23
Alice's result Squaring of 5 Bob's result
---------------- --------------- ---------------
1 1
1 * 5 = 5 <- 1 5 0 -> 1
5 <- 0 5^2 = 2 mod 23 1 -> 1 * 2 = 2
5 * 4 = 20 <- 1 5^4 = 4 0 -> 2
20 <- 0 5^8 = 16 1 -> 2 * 16 = 9
20 * 3 = 14 <- 1 5^16 = 3 mod 23
18 = 9^21 mod 23 (Shared secret) 18 = 14^10 mod 23
Squaring of 9 Alice's result
------------- ---------------
1
9^1 = 9 1 -> 1 * 9 = 9
9^2 = 12 0 -> 9
9^4 = 6 1 -> 9 * 6 = 8
9^8 = 13 0 -> 8
9^16 = 8 1 -> 8 * 8 = 18
Squaring of 14 Bob's Result
-------------- -----------------
1
14^1 = 14 0 -> 1
14^2 = 12 1 -> 1 * 12 = 12
14^4 = 6 0 -> 12
14^8 = 13 1 -> 12 * 13 = 18
The previous page performs exponentiation by operating on the
exponent from right-to-left. Exponentiation can also be performed
by operating on the exponent from left-to-right. This may be more
efficient for small base values, as the multiplications, as
opposed to squarings, are performed only with the base values,
which may be small values. This is illustrated below.
[ 21 dec, 10101 bin ] Alice's secret
14 = 5^21 mod 23 ----------> Sends to Bob 14
Bob's secret [ 10 dec, 1010 bin ]
9 Sends to Alice <---------- 9 = 5^10 mod 23
Alice's public key Bob's public key
------------------------- -------------------------
init: 5 <- 1 init: 5 <- 1
square: 5 * 5 = 2 square: 5 * 5 = 2
square: 2 * 2 = 4 <- 0 square: 2 * 2 = 4 <- 0
mult: 4 * 5 = 20 <- 1 mult: 4 * 5 = 20 <- 1
square: 20 * 20 = 9 square: 20 * 20 = 9 <- 0
square: 9 * 9 = 12 <- 0
mult: 12 * 5 = 14 <- 1
18 = 9^21 mod 23 (Shared secret) 18 = 14^10 mod 23
Alice's shared secret Bob's shared secret
------------------------- -------------------------
init: 9 <- 1 init: 14 <- 1
square: 9 * 9 = 12 square: 14 * 14 = 12
square: 12 * 12 = 6 <- 0 square: 12 * 12 = 6 <- 0
mult: 6 * 9 = 8 <- 1 mult: 6 * 14 = 15 <- 1
square: 8 * 8 = 18 square: 15 * 15 = 18 <- 0
square: 18 * 18 = 2 <- 0
mult: 2 * 9 = 18 <- 1
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: GSM tracking
Date: Fri, 15 Sep 2000 09:41:00 -0600
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]=NOSPAM
says...
>
>
> I know that a mobile phone can be tracked while being used. But there�s
> something I�m not sure about: can a GSM phone be tracked when it�s off, or is it
> necessary to plug the battery away?
I haven't looked very closely at GSM phones as such recently, but
quite a few (especially CDMA phones) continue tracking base stations
even when you turn them off as thoroughly as you can. In quite a few
cases they even have a small, non-removable battery built into the
phone so base stations know where it is even for a while after you
remove the battery. This is done because it can take some time for
the phone to establish its position, list of base stations, etc., and
they'd rather avoid it when possible.
> Also, has the tracking capability been already requested by law
> enforcement bodies (e.g. FBI), or is it the next gift they�ll ask from Santa?
I don't think they need to ask for much: though base stations don't
normally export the data anywhere, it's pretty easily available for
the taking -- it's already been used to do things like find people in
emergencies, so the only hurdles to using it for other purposes are
legal, not technical. I'm not sure, but I suspect current wire-tap
laws would allow doing it assuming they went through "due process" --
I.e. got a court order and such.
--
Later,
Jerry.
The Universe is a figment of its own imagination.
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: Intel's 1.13 MHZ chip
Date: Fri, 15 Sep 2000 09:41:04 -0600
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
[ ... ]
> You have just accused important government officials of squandering
> their agency's limited resources in a most irresponsible manner.
Rather the contrary: as I said, I'm quite certain reasonable uses to
justify the purchases were found after the fact. This happens both
inside and outside of the government on an _extremely_ regular basis.
> Do you have evidence for that accusation?
Oh good lord. I don't put DIRNSA on the pedestal you do, but even
I'm willing to face reality: nobody's going to achieve the position
without being _awfully_ good at intelligence gathering. Bruce
Schneier points out that good cryptographers mostly have to be good
cryptanalysts. The same idea applies here: a good intelligence
gatherer is also certain to be excellent at ensuring against there
being intelligence (I.e. evidence) to gather against him.
> How many generals "came through on tours",
Why would the number have any relevance to anything? If he did to
get bragging rights over one person would that somehow be more
acceptable than if it were 50 (or vice versa)?
> and why would DIRNSA think it important to show
> them big computers instead of good intelligence production?
Because it's about one-upsmanship, not real, useful information.
Face reality: roughly 90% of the decisions in the military are made
for reasons of bragging rights, not because they make any real sense.
Since it happened around the same time frame as we're discussing,
consider the C-17 for a prime example -- most kindly described as
"overpriced spare parts flying in close formation", it never met
specifications, and even if it had, it STILL wouldn't have been
justified, because it provided only a subset of existing capabilities
at increased cost.
--
Later,
Jerry.
The Universe is a figment of its own imagination.
------------------------------
** 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
******************************
