Cryptography-Digest Digest #186, Volume #12 Sun, 9 Jul 00 18:13:00 EDT
Contents:
Re: Efficient algorithm to determine relative primality? (Bryan Olson)
Re: Proposal of some processor instructions for cryptographical (Terje Mathisen)
Re: Using CRC's to pre-process keys (David A. Wagner)
Re: Advanced Cryptography FAQ (James Pate Williams, Jr.)
Re: Proposal of some processor instructions for cryptographical (Mok-Kong Shen)
Re: Proposal of some processor instructions for cryptographical (Iain McClatchie)
Re: Proposal of some processor instructions for cryptographical (Mok-Kong Shen)
Re: Proposal of some processor instructions for cryptographical (Mok-Kong Shen)
Re: Proposal of some processor instructions for cryptographical (Helger Lipmaa)
Re: Proposal of some processor instructions for cryptographical (Mok-Kong Shen)
CP algorithm ("Theophilus Samuels")
Re: Advanced Cryptography FAQ (John Savard)
Re: Proposal of some processor instructions for cryptographical applications (John
Savard)
----------------------------------------------------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Efficient algorithm to determine relative primality?
Date: Sun, 09 Jul 2000 19:58:55 GMT
ChenNelson wrote:
> Would someone know an efficient algorithm for determining whether
> numbers x and y are relatively prime, without havng to necessarily
> calculate gcd(x,y) using Euclid's method? Calculating the gcd of two
> numbers using Euclid's method is too slow for crypto-size (100+digits)
> numbers. Thanks.
I don't think any significantly faster algorithm is known.
Euclid's algorithm* is blazingly fast. The usual
implementation is quadratic in the number of digits,
and much faster than exponentiation.
(*) I assume we're talking about the modern version of
Euclid's algorithm, based on
for x != 0, GCD(x, y) = GCD(x, y mod x).
As I understand things, the ancient Greek version
reduced the problem using
GCD(x, y) = GCD(x, y-x)
which would be slow.
--Bryan
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Terje Mathisen <[EMAIL PROTECTED]>
Crossposted-To: comp.arch
Subject: Re: Proposal of some processor instructions for cryptographical
Date: Sun, 09 Jul 2000 17:36:25 +0200
Mok-Kong Shen wrote:
>
> Terje Mathisen wrote:
>
> > Since future crypto algorithms will work with a minimum block size of
> > 128 bits, this instruction would at the very minimum be capable of
> > working with half that size, i.e. 64-bit registers. A generalized
> > bit-shuffle operation would then need something like 64 * 6 = 384 bits
> > of shuffle index data. (This could theoretically be limited to the
> > number of bits needed to encode 64!, but I would not like to try to
> > dynamically split this at runtime. :-()
>
> I think that 64-bit PCs are in the coming, and the price of 64-bit
> workstations are going down to be affordable to those having serious
> encryption jobs that justify higher expenses. For a 128-bit algorithm,
> 64-bit permutation is not too bad, I suppose, noting that for a Feistel
> cipher one splits the block into two halves. Could you please explain
> why you need 384-bit permutations for a 128-bit algorithm? Thanks.
Please re-read my post above: If each output bit can come from any of
the 64 possible input locations, then it will need a 6-bit number
(0..63) to specify that relationship.
Doing the same for all 64 input/output bits would then require 6*64 =
384 index/routing bits.
So, do you want something like a fixed 6-register block, where the first
register to be used is specified as part of the instruction, or do you
want to have a 384-bit immediate operand to the opcode?
Terje
--
- <[EMAIL PROTECTED]>
Using self-discipline, see http://www.eiffel.com/discipline
"almost all programming can be viewed as an exercise in caching"
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: Using CRC's to pre-process keys
Date: 9 Jul 2000 13:13:02 -0700
In article <[EMAIL PROTECTED]>,
Mack <[EMAIL PROTECTED]> wrote:
> If the 160-bit hash is reduced to 128 bits (again pick your method of
> reducing it) collicions occur after 2^64 inputs. When you reduce your
> key to produce 128 bit output the birthday paradox applies to the
> reduced value not the original value.
Yes, quite right.
> >What's not clear is why this is at all relevant to the application of
> >hashing entropy sources to get key material. I don't know about you,
> >but the number of keys _I_ have ever generated falls far short of 2^80...
>
> Since the original post was about ASCII text key processing I am
> not sure it is.
Er... huh? Sorry, I don't know how to read your comment. Are you
suggesting that you might want to generate more than 2^64 keys in your
life?
------------------------------
From: [EMAIL PROTECTED] (James Pate Williams, Jr.)
Subject: Re: Advanced Cryptography FAQ
Date: Sun, 09 Jul 2000 20:34:31 GMT
On Sun, 09 Jul 2000 19:31:27 GMT, [EMAIL PROTECTED] wrote:
>-------------------------------------------------------
>Advanced Cryptography FAQ (Frequently Asked Questions)
>-------------------------------------------------------
Big cut.
>8. Where can I find documentation on Base Encryption?
>
>http://www.edepot.com/phl.html
>
Not so cleverly disguised shareware spam.
==Pate Williams==
[EMAIL PROTECTED]
http://www.mindspring.com/~pate
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: comp.arch
Subject: Re: Proposal of some processor instructions for cryptographical
Date: Sun, 09 Jul 2000 22:31:29 +0200
"Trevor L. Jackson, III" wrote:
> Mok-Kong Shen wrote:
>
> > Holger Bettag wrote:
> >
> > > Mok-Kong Shen <[EMAIL PROTECTED]> writes:
> > >
> > > > Skipper Smith wrote:
> > > >
> > > > > Have you looked at the AltiVec instructions contained in the MPC7400? You
> > > > > can download the manual from:
> > > > > www.mot.com/SPS/PowerPC/teksupport/teklibrary
> > > >
> > > > It would be nice, if you would give a list of instructions of that processor
> > > > that are particularly relevant for crypto.
> > > >
> > > "Vector permute" would be the most outstanding candidate. Together with
> > > "vector select" and the bitwise shifts/rotates, one can build almost arbitrary
> > > bit permutations.
> >
> > Would you please explain a little bit these instructions and illustrate
> > with a tiny (reduced) example of how to effect an arbitrary permuation?
> > Thanks.
>
> BIT REVERSAL
>
> In the absence of bitfield addressability bit reversing bytes is not at all
> difficult or slow given a 256-byte LUT and the equivalent of an XLAT instruction.
> Even the XLAT is unnecessary.
>
> Since bit reversal has a property of self similarity (larger entities can be
> reversed by swapping and reversing their components), bit reversing words is not
> much harder. One performs the byte translation described above, and then swaps a
> few bytes around. For a 64-bit value the swapping can be performed inline given an
> addressing mechanism of only mediocre flexibility.
>
> On the x86 architecture one can perform the entire swapping process with three MMX
> registers, and by interleaving the LUT access with the swapping I'd guess the whole
> process should take under 20 clocks. This ignores LUT cache latency because either
> you need really high performance bulk bit reversal, in which case the LUT is
> probably in cache, or you are using bit reversal infrequently, in which case there's
> no reason to worry about bit reversal performance.
>
> ARBITRARY PERMUTATION
>
> Imagine an IO device which was a form of bitwise plugboard. One could write an
> arbitrary value to the input port (or memory location) and read back the permuted
> value from the output port (or memory location). Presumably this could operate at
> full CPU speed. With a third port to configure the permutation mechanism, you would
> have a tiny crypto engine to prove the utility of your architectural comments. If
> you wanted to be thorough you would provide enough configuration storage to make
> each output bit an arbitrary function of the input bits.
>
> This kind of device is not hard to create.
I don't understand. I was asking Holger Bettag to explain the instructions
"Vector permute" and "vector select" and how to use these specific
instructions to realize a permutation. Your stuff above seems to be
irrelevant to my question to him.
M. K. Shen
------------------------------
From: Iain McClatchie <[EMAIL PROTECTED]>
Crossposted-To: comp.arch
Subject: Re: Proposal of some processor instructions for cryptographical
Date: Sun, 09 Jul 2000 13:23:04 -0700
Why bother supporting cryptography in the CPU? I agree that general-
purpose substitution and diffusion operations might make software
encryption faster. But why do crytography in software, especially
if you have to hack the hardware ISA to do it?
- Hardware implementations of the speed-critical cyphers are _tiny_.
As an example, check out http://www.10xinc.com/DES.html. The
incremental cost of 0.4 mm^2 on a 0.25u 440BX is less than 1%.
- Popularly-used cryptographic algorithms change very slowly. While
it's true that Compaq is trying to push a new proprietary crypto
algorithm, most crypto professionals talk about having years of
peer review of an algorithm before adopting it for real use.
I think cryptographic algorithms are slow enough to change that
they can be added to the standard PC architecture without ending
up with a lot of unused baggage. Heck, Intel has already added
a random-number generator and a serial number.
- Connection speeds are increasing. Software encryption can keep
up with a 56 Kb/s modem just fine, but a 10 Mb/s cable modem is
a problem, especially when also running bloated browsers, which,
in turn, are simulating Java machines et al.
- Popular cryptographic algorithms now appear to be exportable. The
legal hassles associated with including crypto in standard PC
hardware appear to be diminishing. I think this was the last
problem holding up standard inclusion of crypto, and I would expect
to see crypto hardware supporting IPSec in standard system or
networking chips in the next two years.
All this aside, I don't see widespread hardware implementation of
public-key cryptography anytime soon. Since it's only used during
secure connection setup, processors can do it fast enough for PC
use. Edge routers and firewalls are a different story -- they're
using hardware public-key cryptography right now.
-Iain McClatchie 650-364-0520 voice
http://www.10xinc.com 650-364-0530 FAX
[EMAIL PROTECTED] 650-906-8832 cell
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: comp.arch
Subject: Re: Proposal of some processor instructions for cryptographical
Date: Sun, 09 Jul 2000 23:15:09 +0200
Terje Mathisen wrote:
> Mok-Kong Shen wrote:
> >
> > Terje Mathisen wrote:
> >
> > > Since future crypto algorithms will work with a minimum block size of
> > > 128 bits, this instruction would at the very minimum be capable of
> > > working with half that size, i.e. 64-bit registers. A generalized
> > > bit-shuffle operation would then need something like 64 * 6 = 384 bits
> > > of shuffle index data. (This could theoretically be limited to the
> > > number of bits needed to encode 64!, but I would not like to try to
> > > dynamically split this at runtime. :-()
> >
> > I think that 64-bit PCs are in the coming, and the price of 64-bit
> > workstations are going down to be affordable to those having serious
> > encryption jobs that justify higher expenses. For a 128-bit algorithm,
> > 64-bit permutation is not too bad, I suppose, noting that for a Feistel
> > cipher one splits the block into two halves. Could you please explain
> > why you need 384-bit permutations for a 128-bit algorithm? Thanks.
>
> Please re-read my post above: If each output bit can come from any of
> the 64 possible input locations, then it will need a 6-bit number
> (0..63) to specify that relationship.
>
> Doing the same for all 64 input/output bits would then require 6*64 =
> 384 index/routing bits.
>
> So, do you want something like a fixed 6-register block, where the first
> register to be used is specified as part of the instruction, or do you
> want to have a 384-bit immediate operand to the opcode?
I now understand. You mean one needs 384 bits as an operand to
be supplied to the instruction. I would even be ready to use 8*64 bits,
i.e. letting each bit position be specified in one byte which may be more
convenient to handle. This operand, being large, is in memory and is
referenced by address.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Proposal of some processor instructions for cryptographical
Date: Sun, 09 Jul 2000 23:15:17 +0200
Samuel Paik wrote:
> My editing seems to have gone out the window. Let me try again...
>
> Mok-Kong Shen wrote:
> > Actually I don't think that a general bit permuation instruction is very
> > extravagant. There is, if I don't err, normally a translate instruction that
> > does bytewise substitutions according to an array of 256 elements.
>
> Can you name a general purpose CPU architecture introduced in the last
> twenty-five years with such an instruction?
I can't (at least without searching). In fact, my knowledge of machine
instructions is very out-dated, because I haven't been doing assembly
programming since decades.
> While we can imagine uses for a transposition instruction, a concrete
> example of an algorithm implementation showing
> a) how it is implemented today,
> b) how it would be implemented with some specific proposal
> c) an argument on the performance and cost differences
> between the two (generally, performance = time, cost = memory space)
> might be illuminating.
In my (maybe outdated) programming style I would for the most
general case use a mask to get each bit and shift it to its new location
and finally OR these results together to obtain the permutation. That
would be more expensive than a specially designed instruction, I
believe.
M. K. Shen
------------------------------
From: Helger Lipmaa <[EMAIL PROTECTED]>
Crossposted-To: comp.arch
Subject: Re: Proposal of some processor instructions for cryptographical
Date: Mon, 10 Jul 2000 02:16:54 +0300
>
Finite field GF(2^8) and GF(2^16) multiplication (modulo some fixed irreducible
polynomial) would be nice. May be also some other operations (x->x^-1, e.g.).
Several AES finalists (Rijndael, Twofish, MARS) would accelerate considerably if the
next block of four 32-bit memory references could be computed by one instruction:
A:=table[(X>>0)&255 + C1*256]
B:=table[(X>>8)&255 + C2*256]
C:=table[(X>>16)&255 + C3*256]
D:=table[(X>>24)&255 + C4*256]
(where 0<=Ci<=15, and A, B, C, D, X are 32-bit registers).
Rijndael's rounds basically consist of four such blocks of instructions plus a 128-bit
xor. Twofish has two such blocks + some spice per round. Every forward-mix and
backward-mix round of MARS consists of one such block + some rotations.
Imagine that a 128-bit processor, featuring two memory-read ports, executes such block
in 2 cycles. Then every round of Rijndael would take only 9 cycles, and hence
Rijndael128
would execute in (slightly more than 90) cycles.
Helger Lipmaa
http://www.tcm.hut.fi/~helger
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: comp.arch
Subject: Re: Proposal of some processor instructions for cryptographical
Date: Sun, 09 Jul 2000 23:30:14 +0200
Iain McClatchie wrote:
> Why bother supporting cryptography in the CPU? I agree that general-
> purpose substitution and diffusion operations might make software
> encryption faster. But why do crytography in software, especially
> if you have to hack the hardware ISA to do it?
One may want to use algorithms that don't have specific hardware
implementations. (Not everyone agrees which is THE best algorithm.)
One saves the cost of the hardware. A very personal reason is that I
have more confidence in software code that I can examine than in a
piece of hardware that I can't examine.
M. K. Shen
------------------------------
From: "Theophilus Samuels" <[EMAIL PROTECTED]>
Subject: CP algorithm
Date: Sun, 9 Jul 2000 22:55:15 +0100
Check out http://www.cayley-purser.ie for an article entitled 'Cryptography:
An Investigation of a New Algorithm vs. the RSA' - this was written by Sarah
Flannery who won Ireland's Young Scientist of the Year award 1999. If this
has already been discussed beforehand, then forgive my intrusion.
T.L.S.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Advanced Cryptography FAQ
Date: Sun, 09 Jul 2000 21:59:03 GMT
On Sun, 09 Jul 2000 19:31:27 GMT, [EMAIL PROTECTED] wrote, in part:
>1) Those that want to have something (anything!!!) to do with it
> to steal credit or get some personal gain as base encryption
> revolutionizes the cryptography world.
Long before you visited this newsgroup, one participant was (on a
consistent basis) advocating the use of different bases for
encryption. My web site even discusses ways to use efficient
translations between bases for encryption in two places: one where I
outline a scheme for converting between 47 bits and 10 letters, and
one where I show how a conventional block cipher could incorporate
base conversion (in its F-function) and still produce a binary output
the same size as its binary input.
However, as you've explained things here, you have come up with an
idea that is original, as far as I know. Have the bases used in
encryption be part of the key.
You are quite right: that would make many existing forms of
cryptanalysis obsolete, and, if properly done, would not create new
ones.
There are two fundamental problems, though:
- The conversion from one base to another is never perfect, so there
would be frequency-count evidence of which one was the last base used,
when the final form of the message was converted to some standard base
for transmission;
- The number of bases that can be used is limited: thus, a cipher
would have to have several stages, each with a different base,
otherwise an attacker could simply mount a complete attack on each
possibility.
While this is a nice idea, though, claiming that it will
"revolutionize cryptography", and that it isn't possible to design
secure ciphers without it, only serves to earn dismissal for yourself
and your idea. It's not really clear that changing bases mixes things
up that much more than the use of S-boxes which directly fit the base
being used. And ciphers such as the AES candidates certainly look
impressive enough that the experts in the field - people with
impressive academic credentials, and well-earned reputations for
intelligence and honesty - do not find them inadequate.
John Savard (teneerf <-)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Crossposted-To: comp.arch
Subject: Re: Proposal of some processor instructions for cryptographical applications
Date: Sun, 09 Jul 2000 22:04:21 GMT
On Sun, 09 Jul 2000 12:06:09 -0400, "Douglas A. Gwyn"
<[EMAIL PROTECTED]> wrote, in part:
>Mok-Kong Shen wrote:
>> I think that 64-bit PCs are in the coming, and the price of 64-bit
>> workstations are going down to be affordable to those having serious
>> encryption jobs that justify higher expenses.
>Many of us have been using architectures with 64-bit words on our
>desktops for several years now.
Me, I'm just annoyed that the new IA-64 architecture from Intel, which
puts three instructions in a 128-bit block,
- doesn't use a 128-bit data bus, and a new set of MMX-type
instructions to exploit it, to keep up with Motorola's AltiVec, and
- provides population count, a general 16-bit subblock transpose, and
some useful fixed byte transposes, but no bit transposes.
It comes so close to being a supercomputer on a chip...
John Savard (teneerf <-)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
** 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
******************************
