Cryptography-Digest Digest #644, Volume #11 Thu, 27 Apr 00 09:13:01 EDT
Contents:
Karatsuba threshold (Francois Grieu)
Re: factor large composite (Runu Knips)
Re: Magnetic Remenance on hard drives. (Jonathan Thornburg)
Re: Help: encrypting bit fields (Runu Knips)
Re: Karatsuba threshold (Scott Contini)
Re: Karatsuba threshold (Jonathan Thornburg)
Re: Help: encrypting bit fields (Volker Hetzer)
Re: Looking for a *simple* C Twofish source (Runu Knips)
RE: AEES 16 rounds ("Manuel Pancorbo")
Re: Magnetic Remenance on hard drives. (was: Re: Evidence Eliminator - (jungle)
Re: Karatsuba threshold (Francois Grieu)
RE: AEES 16 rounds ([EMAIL PROTECTED])
Re: Magnetic Remenance on hard drives. ([EMAIL PROTECTED])
Re: Karatsuba threshold (Mark Wooding)
----------------------------------------------------------------------------
From: Francois Grieu <[EMAIL PROTECTED]>
Subject: Karatsuba threshold
Date: Thu, 27 Apr 2000 11:52:17 +0200
I assume we multiply two numbers of n*w bits each, giving a result of
2*n*w bits (at most) with a general purpose computer of word size w
bits, with hardware that can multiply two w bits integers giving a 2*w
bits integer in a few cycles.
The classical multiplication algorithm performs n^2 multiplications and
has execution time O(n^2)
The Karatsuba multiplication method [1] (or variants [2]) has execution
time O(n^1.5)
Above some threshold for n, Karatsuba multiplication beats classical
multiplication, and I am seeking experimental estimations of this
"Karatsuba threshold".
GMP defaults to a KARATSUBA_THRESHOLD of 8, but Knuth says 2 on most
architectures. Any other estimations out there ?
Also, what are the next thresolds, like when does Toom-Cook [3] or FFT
multiplication [4] becomes usefull ?
Francois Grieu
[1] <http://mathworld.wolfram.com/KaratsubaMultiplication.html>
[2] Knuth TAOCP Vol 2, 4.3.3 A
[3] Knuth TAOCP Vol 2, 4.3.3 Alg T
[4] Knuth TAOCP Vol 2, 4.3.3 C
------------------------------
Date: Thu, 27 Apr 2000 12:01:06 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: factor large composite
Johnny Bravo wrote:
> The cost is nothing, ...
Wrong. If your CPU is idle, it will execute a HLT and waste far
less power. If you always have some low priority task running
which uses every bit of time he can get, you will waste far more
power than without it.
Plus, no matter how low the priority of such a program is, it
will always fill the CPU cache with its instructions and drop
other peoples stuff out of it. This effect is real; you can
experience it in practice.
------------------------------
From: [EMAIL PROTECTED] (Jonathan Thornburg)
Subject: Re: Magnetic Remenance on hard drives.
Date: 27 Apr 2000 12:15:09 +0200
In article <8e7ar3$629$[EMAIL PROTECTED]>,
I (Jonathan Thornburg <[EMAIL PROTECTED]>) pointed out that
> ## http://www.cs.auckland.ac.nz/~pgut001/pubs/secure_del.html
>
> Secure Deletion of Data from Magnetic and Solid-State Memory
>
> Peter Gutmann
> Department of Computer Science
> University of Auckland
> [EMAIL PROTECTED]
>
> This paper was first published in the Sixth USENIX Security Symposium
> Proceedings, San Jose, California, July 22-25, 1996
> explains how/why data recovery *is* both possible and practical,
> in some detail.
In article <A%HN4.59460$[EMAIL PROTECTED]>,
<[EMAIL PROTECTED]> replied
> The paper given above does
>not contain any expirimental results.
Well, not quite. It does, however, contain fairly detailed descriptions
of some data-recovery techniques, enough to allow rough estimates of
their cost and practicality.
Moreover, if you look in the parent directory on the author's web site,
to wit http://www.cs.auckland.ac.nz/~pgut001/ , you find the following
description referring to the above paper [[emphasis added]]:
> * A paper on the Secure Deletion of Data from Magnetic and
> Solid-State Memory, which exposes a number of myths about the
> deletion of data, shows how data can be recovered long after it
> should have been erased, and indicates a method of erasure which
> should make it a considerable challenge to recover any deleted
> data. This paper was presented at the 1996 Usenix Security
> Symposium, but you had to attend the conference to see the cool
========
> colour slides of supposedly overwritten disk data which wasn't
==============================================================
> really overwritten (they were too big to fit in the paper itself).
==================
--
-- Jonathan Thornburg <[EMAIL PROTECTED]>
http://www.thp.univie.ac.at/~jthorn/home.html
Universitaet Wien (Vienna, Austria) / Institut fuer Theoretische Physik
"Most investment bankers' [...] idea of a long-term investment
is thirty-six hours" -- Robert Townsend, "Up the Organization"
------------------------------
Date: Thu, 27 Apr 2000 12:13:05 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: Help: encrypting bit fields
Paul Rubin wrote:
> Say I want to encrypt a bit field (37 bits, for example) and get
> back another 37-bit field. E.g. I want to simulate a 37-bit codebook
> cipher. Alternatively, say I want to encrypt an integer range, such
> as 10-digit decimal integers.
Can anyone explain to me why he doesn't just use CFB mode ?
That is:
P(x): plaintext x ENC(n): encryption
C(x): ciphertext x DEC(n): decryption (not used)
IV : initialisation vector/block
Encryption:
C(1) := ENC(IV) XOR P(1)
C(n) := ENC(C(n-1)) XOR P(n)
Decryption:
P(1) := ENC(IV) XOR C(1)
P(n) := ENC(C(n-1)) XOR C(n)
(Instead of XOR, one could use any other invertable function,
such as + and - etc)
Or use any stream cipher - whats the problem ?
------------------------------
From: [EMAIL PROTECTED] (Scott Contini)
Subject: Re: Karatsuba threshold
Date: 27 Apr 2000 10:21:34 GMT
In article <[EMAIL PROTECTED]>,
Francois Grieu <[EMAIL PROTECTED]> wrote:
>I assume we multiply two numbers of n*w bits each, giving a result of
>2*n*w bits (at most) with a general purpose computer of word size w
>bits, with hardware that can multiply two w bits integers giving a 2*w
>bits integer in a few cycles.
>
>The classical multiplication algorithm performs n^2 multiplications and
>has execution time O(n^2)
>
>The Karatsuba multiplication method [1] (or variants [2]) has execution
>time O(n^1.5)
>
Shouldn't that be n^(lg 3) where "lg" is log base 2?
>Above some threshold for n, Karatsuba multiplication beats classical
>multiplication, and I am seeking experimental estimations of this
>"Karatsuba threshold".
>
>GMP defaults to a KARATSUBA_THRESHOLD of 8, but Knuth says 2 on most
>architectures. Any other estimations out there ?
>
>Also, what are the next thresolds, like when does Toom-Cook [3] or FFT
>multiplication [4] becomes usefull ?
>
Actually I am quite surprised that you read about thresholds as low as
2 and 8. I worked with Arjen Lenstra's LIP arithmetic package, which
(based on my judgement) has an extremely efficient Karatsuba implementation,
as well as a pretty darn good classical multiplication implementation.
Depending on the architecture, I found that the Karatsuba overlap was
somewhere between 15 and 30, if my memory is accurate (which it may
not be). Note that the Karatsuba works recursively: it breaks it
down to 3 multiplications of size n/2 - and the smaller multiplies
will be done by Karatsuba also if and only if they are greater than
the threshold (otherwise they are done with classical multiply).
Moreover, two of the recursive calls are actually squaring operations -
so one should have optimized Karatsuba squaring and optimized classical
multiply squaring (taking advantage of symmetry).
I had written a timer program that works with LIP and determines
the optimal threshold for the Karatsuba. I'm not sure if this timer
program is still being distributed with LIP or not, but if you're
interested in it, you could probably get it from Arjen.
I don't have any experience with Toom-Cook or FFT.
Scott
------------------------------
From: [EMAIL PROTECTED] (Jonathan Thornburg)
Subject: Re: Karatsuba threshold
Date: 27 Apr 2000 12:21:54 +0200
In article <[EMAIL PROTECTED]>,
Francois Grieu <[EMAIL PROTECTED]> wrote:
>Above some threshold for n [[number of words per number]],
>Karatsuba multiplication beats classical
>multiplication, and I am seeking experimental estimations of this
>"Karatsuba threshold".
>
>GMP defaults to a KARATSUBA_THRESHOLD of 8, but Knuth says 2 on most
>architectures. Any other estimations out there ?
>
>Also, what are the next thresolds, like when does Toom-Cook [3] or FFT
>multiplication [4] becomes usefull ?
You have to experiment -- the thresholds depend sensitively on the
constant factors in those O(...) performances, i.e. on the details
of the various methods implementations. However, the
performance = fn(threshold) curves tend to be fairly flat around
the optima.
The best solution is often a per-platform autoconfigure which builds
the code with a variety of thresholds, tests them, then chooses the
fastest.
--
-- Jonathan Thornburg <[EMAIL PROTECTED]>
http://www.thp.univie.ac.at/~jthorn/home.html
Universitaet Wien (Vienna, Austria) / Institut fuer Theoretische Physik
"The first strike in the American Colonies was in 1776 in Philadelphia,
when [...] carpenters demanded a 72-hour week." -- Anatole Beck
------------------------------
From: Volker Hetzer <[EMAIL PROTECTED]>
Subject: Re: Help: encrypting bit fields
Date: Thu, 27 Apr 2000 10:39:06 +0000
Runu Knips wrote:
> Can anyone explain to me why he doesn't just use CFB mode ?
Because of the block size of 37Bit?
> Or use any stream cipher - whats the problem ?
For a stream cipher you have to guarantee that you don't
reuse a key stream. That means some kind of synchronizing
between the encryptor and the decryptor. If he does not
encrypt a communications channel that might not be
possible for him.
Greetings!
Volker
--
Hi! I'm a signature virus! Copy me into your signature file to help me spread!
------------------------------
Date: Thu, 27 Apr 2000 12:46:33 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: Looking for a *simple* C Twofish source
[EMAIL PROTECTED] schrieb:
> I was aware of the all the free sources you've mentioned. I cannot
> compile or use things like "u4byte mk_tab[4][256]" (that's a lot of
> RAM too!), let alone "q8(q8(q8(q8(x, 4, n), 3 ,n), 2, n), 1, n)" (from
> brian gladman's implementation).
> Unfortunately I am not a cryptologist and going through the Twofish AES
> paper does not help me figure out how to implement the algorithm, since
> it is missing a much-needed pseudo-code example. One has to deeply
> understand all the math details, and closely follow the figures before
> going ahead with any coding. Compare with RC6 (or TEA...)
I would then suggest you recode gladman's implementation in a way
which decomposes all complex statements and puts them into temporary
variables. Remember you have to undefine all four defines at the
top of it.
Ouch. Or maybe use (or mix it with) Tom St.Denis Cryptobag. Hey,
Tom, your webpage is completely chaotic. Where is the link to the
actual CryptoBag ???
------------------------------
From: "Manuel Pancorbo" <[EMAIL PROTECTED]>
Subject: RE: AEES 16 rounds
Date: Thu, 27 Apr 2000 12:14:33 +0200
<[EMAIL PROTECTED]> escribi� en el mensaje de noticias
8e6lle$p3n$[EMAIL PROTECTED]
> AEES is symmetric encryption algorithm, which is developed from the
> DES architecture.
>
Why don't you submit it to sci.crypt Cipher Contest?
http://www.wizard.net/~echo/crypto-contest.html
>
>
> Performance with my IP II,267 Mhz, 128 Mb is 101 Kb/sec.
>
A bit slow, isn't it?
--
____________________________________________________________________________
_________
Manuel Pancorbo
[EMAIL PROTECTED]
"...
M�s vale aprender una sola l�nea de Ciencia
que postrarse cien veces en oraci�n. (Cor�n)
Pli valoras lerni ech nur unu linion de Scienco
ol preghe genui cent fojojn. (Korano)
..."
____________________________________________________________________________
_________
------------------------------
From: jungle <[EMAIL PROTECTED]>
Subject: Re: Magnetic Remenance on hard drives. (was: Re: Evidence Eliminator -
Date: Thu, 27 Apr 2000 07:24:00 -0400
I didn't get it ...
"data on paper" ? OR text on paper ?
"resist is" ? OR resist it ?
Arturo wrote:
> On Thu, 27 Apr 2000 02:36:03 -0400, jungle <[EMAIL PROTECTED]> wrote:
> >"NFN NMI L." wrote:
> >> he notes that
> >> recovering data is mostly possible.
> >yap, on paper ...
> Not if the paper is damaged. If it�s not, the process of recovering
> data on paper is easy: it is called reading.
> (Sorry, could not resist is .. ;-) )
sorry for what ?
------------------------------
From: Francois Grieu <[EMAIL PROTECTED]>
Subject: Re: Karatsuba threshold
Date: Thu, 27 Apr 2000 14:00:27 +0200
[EMAIL PROTECTED] (Scott Contini) wrote:
>> The Karatsuba multiplication method has execution time O(n^1.5)
> Shouldn't that be n^(lg 3) where "lg" is log base 2?
Scott is positively right, that is O(n^1.585..)
> Actually I am quite surprised that you read about thresholds as
> low as 2 and 8.
Knuth writes:
"[Karatsuba variant (*)] can be used to multiply double-precision
inputs when we want a quadruple precison result, and it will be
just a little faster than the traditional method on many machines"
However he does say "many", not "most" as I originaly reported
(another error in my original post).
> the Karatsuba overlap was somewhere between 15 and 30
That enormous variation (2-30) for the Karatsuba thresold bothers me.
Maybe one cause of dispredancy is that the thresold when doing straight
multiplication is well below the one when doing modular exponentiation
as in RSA, which is often the target application. This difference is
because one can use the classical algorithms in a "multiply and reduce"
which cost is markedly below 2 multiplications (**), and using Karatsuba
this goes to 3 multiplications (***).
Francois Grieu
(*) For those who wonder, Knuth's Karatsuba variant avoids to multiply
numbers one bit wider than each half, as does the original Karatsuba
technique.
(**) neglecting quotient estimation, the classic algorithms for
multiplication and modular reduction have the same cost; and when doing
simulataneous multiply and reduce, one can save on operand accesses.
(***) one pre-computes the inverse of the modulus; then after each
multiplication, quotient estimation (within 3) costs a multiplication,
and modular reduction itself another.
------------------------------
From: [EMAIL PROTECTED]
Subject: RE: AEES 16 rounds
Date: Thu, 27 Apr 2000 12:04:49 GMT
Manuel,
Thank you very much for your reply.
#Why don't you submit it to sci.crypt Cipher Contest?
Delphi source code is not exceptable and I am not sure
If I understand this challenge. From the two attendees
in the list of this contest one (Boris) is my friend. Boris
developed this encryption more then one year ago and
what is a result of this contest?
Honestly I don't like most from the crowd in sci.crypt.
#A bit slow, isn't it?
It is very hard to check if for this architecture there is
an implementation with better performance.
But I am working on this.
Best regards.
Alexander Ernst.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Magnetic Remenance on hard drives.
Date: Thu, 27 Apr 2000 12:28:21 GMT
Try this one.
Let me choose the make and model of floppy drive used. Both will be
commercial off-the-shelf models. We'll put one drive in Computer A and
put the other drive in Computer B. Allow me to "age" either drive
by running it through duty cycles equivalent to mormal usage over time.
Allow me to format a floppy on either drive. Now put the floppy in
drive A and fill it up with several ASCII data files. Now take that
floppy to Computer B and run a 3 pass PGP wipe.
Give the disk to me. If I can retrieve one percent of the data on the
disk, you give me a million bucks. If I fail, then the cost of retrival
is on me.
The requirement to protect state secrets is orders of magnitude more
stringent than the ability to recover lost data. In the former, any
small piece of data can be very damaging to national security. In the
later, the recovery usually must be a significant percentage of the
loss.
Furthermore, I am certain that if the military can retrieve a 3 pass PGP
wipe, the intelligence windfall from the capability will FAR OUTWEIGH
any commercial benefit.
If the information on that floppy allows your enemy to take
millions from you, would you really feel safe with just a 3 pass PGP
wipe? If your answer is yes, how about taking me up on my
offer? Floppies cost pennies. If you really want to protect the
information on that floppy, burn it.
In article <[EMAIL PROTECTED]>,
jungle <[EMAIL PROTECTED]> wrote:
> in the past, several of the market data recovery companies refused to
attempt
> to recover data wiped by pgp 3 pass from floppy disk ...
>
> without even trying to attempt it ...
>
> this is just A PAPER, PAPER FANTASY ... or academic dislocation ...
>
> I have to this day the floppy that has been wiped [ by accident ] by
one of the
> company employers ...
>
> do you like to help to recover data from it ?
> it is just a floppy disk ... wiped only with 3 passes under pgp ...
>
> Jonathan Thornburg wrote:
> >
> > In article <[EMAIL PROTECTED]>,
> > Trevor L. Jackson, III <[EMAIL PROTECTED]> wrote:
> > >Do you have a reference handy?
> >
> > It's not a commercial service, but
> >
> > > ## http://www.cs.auckland.ac.nz/~pgut001/pubs/secure_del.html
> > >
> > > Secure Deletion of Data from Magnetic and Solid-State
Memory
> > >
> > > Peter Gutmann
> > > Department of Computer Science
> > > University of Auckland
> > > [EMAIL PROTECTED]
> > >
> > > This paper was first published in the Sixth USENIX Security
Symposium
> > > Proceedings, San Jose, California, July 22-25, 1996
> >
> > explains how/why data recovery *is* both possible and practical,
> > in some detail.
>
>
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Karatsuba threshold
Date: 27 Apr 2000 13:06:45 GMT
Scott Contini <[EMAIL PROTECTED]> wrote:
> Moreover, two of the recursive calls are actually squaring operations -
> so one should have optimized Karatsuba squaring and optimized classical
> multiply squaring (taking advantage of symmetry).
Err. I thought that Karatsuba-Ofman worked on the identity
(u b + v)(x b + y) == u x b^2 + ((u + v)(x + y) - u x - v y) b + v y
(where b is some convenient value about half the size of each of the two
numbers being multiplied).
The three multiplications are, then, u x, v y and (u + v)(x + y). None
of these looks like a squaring to me. Of course, if I'm wrong, I get an
opportunity to improve my MP library's performance. ;-)
-- [mdw]
------------------------------
** 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
******************************
