Cryptography-Digest Digest #915, Volume #12 Sat, 14 Oct 00 01:13:01 EDT
Contents:
block-cipher silly question? (N. Weicher)
Re: block-cipher silly question? (David Schwartz)
Re: Problem with SHA256 implementation (Daniel Leonard)
Re: Why trust root CAs ? ([EMAIL PROTECTED])
Re: Is it trivial for NSA to crack these ciphers? (lcs Mixmaster Remailer)
Re: Crypto technology recommendations? (David A Molnar)
Optimisation of SHA-256 (Daniel =?iso-8859-1?Q?L=E9onard?=)
Re: Storing an Integer on a stream (Benjamin Goldberg)
Re: Looking for paper (Benjamin Goldberg)
Re: Looking for paper (Benjamin Goldberg)
Re: Possible secure CRC using shrinking? (Benjamin Goldberg)
Re: The science of secrecy: Simple Substition cipher (Benjamin Goldberg)
Re: working with huge numbers (Benjamin Goldberg)
Re: Why trust root CAs ? (Greggy)
----------------------------------------------------------------------------
From: N. Weicher <[EMAIL PROTECTED]>
Subject: block-cipher silly question?
Reply-To: [EMAIL PROTECTED]
Date: Sat, 14 Oct 2000 02:21:39 GMT
I hope this isn't too silly a question to ask, but is there such a
thing as a credible block cipher that works on a single-byte block?
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: block-cipher silly question?
Date: Fri, 13 Oct 2000 19:37:08 -0700
"N. Weicher" wrote:
> I hope this isn't too silly a question to ask, but is there such a
> thing as a credible block cipher that works on a single-byte block?
Usually we would call such a thing a stream cipher. Obviously, a cipher
that has a fixed input block to output block mapping would be unsuitable
for such a thing.
DS
------------------------------
From: Daniel Leonard <[EMAIL PROTECTED]>
Subject: Re: Problem with SHA256 implementation
Date: Sat, 14 Oct 2000 03:06:05 GMT
On Sat, 14 Oct 2000, Tom St Denis wrote:
> > My code was posted as a zip archive in one of my post (from
> > [EMAIL PROTECTED]) - I know about posting binaries on non-binaries
> group.
> >
> > Now I am trying to implement a less naive implementation.
>=20
> Your code was in Java or C?
>=20
> Tom
My code is in Java, it is the last of "bored of AES" thread.
==========
Daniel L=E9onard
OGMP Informatics Division E-Mail: [EMAIL PROTECTED]
D=E9partement de Biochimie Tel : (514) 343-6111 ext 5149
Universit=E9 de Montr=E9al Fax : (514) 343-2210
Montr=E9al, Quebec Office: Pavillon Principal G-312
Canada H3C 3J7 WWW : http://megasun.bch.umontreal.ca/~leonard
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Why trust root CAs ?
Date: Sat, 14 Oct 2000 04:16:34 GMT
On Sun, 08 Oct 2000 05:10:53 +0100, David Hopwood
<[EMAIL PROTECTED]> wrote:
>-----BEGIN PGP SIGNED MESSAGE-----
>
>Daniel James wrote:
>> In article <[EMAIL PROTECTED]>, Bruce Stephens wrote:
>> > ["Secrets and Lies", Bruce Schneier] pp.238-239.
>> >
>> > "Digital certificates provide no actual security for electronic
>> > commerce; it's a complete sham."
>>
>> Yes, Bruce likes saying that - he comes across as very sceptical of any
>> benefits claimed for PKIs and certificates.
>>
>> As things stand today he's right - certificates are used as a guarantee
>> of a party's identity, and not a very good guarantee at that. It doesn't
>> have to be this way.
>>
>> Imagine, if your bank gave you a smartcard as a credit card, and that
>> card contained a private key you could use to sign messages,
>
>To do that you would need a trustworthy interface to the card that allowed
>you to preview and confirm what is to be signed; a PC is inadequate for
>that because it's not secure. However, let's assume that problem were solved
>somehow. (I suspect that it won't actually be solved, just brushed under the
>carpet :-( )
>
>> a certificate
>> for that key signed by the bank, and the bank's CA certificate. The bank
>> could then say that they wouldn't accept any payment made by you unless it
>> was signed with your key, and that any correctly signed payment *must* have
>> come from you so your card account would be debited even if you denied
>> making the payment.
>
>In that case the certificate and the use of a CA are superfluous; the bank
>could just as easily store your public key in their database record for
>your account. That would be simpler, more efficient, and it would eliminate
>a number of potential failure modes (attacks against the certification
>standard, compromise of the bank's CA key, any problems in matching
>certificate attributes to database records, etc.) Remember that the bank
>already has to store a PIN for each card, so storing a public key instead
>(or as well) is a straightforward change. There is no advantage to the bank
>in using certificates.
This model can be further generalised.
Let's suppose you generate your own public key and register it with
your bank at time of opening your account. Then whenever you sign a
transaction with your private key, your bank knows it is you.
But this could also apply to any other situation where a signature (or
any other verification of identity) is currently required - simply
register your public key and then use your private key to authenticate
your identity in all transactions with that party from then on.
This could extend to verifying your identity to hardware. Your car,
your house locks, all these could be built to enable you to initially
register a public key and only open/operate from that point on when a
random session id is returned signed by the private key corresponding
to your public key.
It could also apply to software - replacing the need for all the
myriad passwords one accumulates for different systems, as you could
associate your public key with your various computer userids on each
system and then return a signed random session ID to verify yourself
at logon.
Furthermore, for those concerned with privacy and the fact that the
public key is a unique id across all applications, enabling traffic
analysis of your movements, habits and usage, one could simply allow
that any person can have as many public keys as they want. This could
present problems for the user in remembering which key they'd
registered with which entity/device, but then we manage to handle a
number of different house keys, car keys passwords etc etc.
But lets suppose that:
. the method of carrying and issuing the public key and storing and
using the private key is a PIN protected or bio-recognition smart card
. they cost $9 apiece at your local newsagent;
. come in a security sealed package from reputable suppliers;
. there is common software/hardware to enable you to generate or
load your own key;
. they have a roughened front surface on which you can write Car,
House, Third National Bank, HomePC, WorkID etc etc, and
. a hole drilled in the top right to enable them to be kept on a key
ring...
I have neglected issues of card loss, key revocation etc etc, but I
dont think these are insurmountable.
As I understand it the major barrier to this approach is that there is
no universal, simple, secure, portable thingy that can carry the keys,
and do the processing required. The obvious candidate is a smart
card, but I understand they simply do not (yet) have the processing
power to handle digital signing using an assymetric key (eg RSA).
Offloading the processing presumably creates security problems.
PB
>- --
>David Hopwood <[EMAIL PROTECTED]>
>
>Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
>RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
>Nothing in this message is intended to be legally binding. If I revoke a
>public key but refuse to specify why, it is because the private key has been
>seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
>
>
>-----BEGIN PGP SIGNATURE-----
>Version: 2.6.3i
>Charset: noconv
>
>iQEVAwUBOd+BhzkCAxeYt5gVAQEqEAf/RCjAXabrazj+oceIj+d8/WC/I+91mHwc
>P5URHoux22bLAN8XOWBe0TK04UVwtR1d0Pt/mA1S1svTbrJ+JAFH3hR1hrr/88eU
>Z1MwH+lbK96oYZbN6sSI3gmvyg/zPS4zXkgW6L9WJfP4Na6wrcjvAH1E9kpGlWcD
>UtzO+ida9CsKo63FW9KZ+nCBvztt1iqZSZI7v/XSfXL35VuzvJq30JPKeyiSA7Lr
>2TqH6v4mma6Scph641KnLWH1BNBavyq2jTvbix5aWkiFnTFvrsAQvpAeGPlsYB0W
>+fOuDdEbmOIowjR/oMR0A+kZ7lDDhhgkwYvQ4mLvEKsCXr2Obq2DEw==
>=+OuX
>-----END PGP SIGNATURE-----
>
------------------------------
Date: 14 Oct 2000 03:20:04 -0000
From: lcs Mixmaster Remailer <[EMAIL PROTECTED]>
Subject: Re: Is it trivial for NSA to crack these ciphers?
>> Aren't you forgetting the obvious fact that these "alphabet soup agencies" don't
>use any
>> of these ciphers to conceal data that is important to them?
>Different problems get different solutions. It's really that simple.
So classified data gets a classified cipher? Or classified data gets a better cipher?
What's "better". That all I'm asking.
>In any event, political arguments like this really don't belong on
>sci.crypt. Take this to talk.politics.crypto.
Is it a political statement to say that if these ciphers aren't good enough for NSA,
they're not good enough for me?
It's not off topic if we're speculating about the speed that the NSA could crack these
ciphers, is it?
The NSA knew how to strengthen DES against differential cryptanalysis many years
before the civilian world knew what it was. I'm simply asking people to speculate
about what tools beyond teraflop computing horsepower that NSA can bring to bear on
these ciphers.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Crypto technology recommendations?
Date: 14 Oct 2000 03:06:28 GMT
Will Newland <[EMAIL PROTECTED]> wrote:
> C-based
> libs. I'm not certain if their pick is because of some techincal
> superiority or just
> their Borg-like adherence to all things M$. I'm willing to listen, though.
> Let me know
> what you think.
There's also the Java Cryptix toolkit http://www.cryptix.org/
On the C++ front, Wei Dai's Crypto++ 3.2 deserves a serious look.
http://www.eskimo.com/~weidai/
I have not reviewed the Cryptix license, but the splash page says "free
for both commercial and non-commercial use."
The advantage of this over a toolkit like Certicom or RSA's toolkit,
in the post-patent era, is no need to shell out $$ at the beginning.
I imagine that the advantage of a commercial vendor's toolkit lies
in the service and support which can be guaranteed, but I haven't
made any study of this.
Adam Shostack used to have a page comparing various crypto toolkits.
I don't know if it's been updated recently.
-David
------------------------------
From: Daniel =?iso-8859-1?Q?L=E9onard?= <[EMAIL PROTECTED]>
Subject: Optimisation of SHA-256
Date: Sat, 14 Oct 2000 00:08:15 -0400
Some people (including me) already implemented SHA-256.
The compression function of SHA-256 looks like the one in SHA-1 and
RIPEMD-160. They look alike because after each pass, they shuffle and
modify their registers. I saw a implementation of such algorithm with
"assignment" shuffling, SHA-1 for example:
e += ((a << 5) | (a >>> 27)) + F1(b, c, d) + W[ 0]; b = ((b << 30)
| (b >>> 2));
d += ((e << 5) | (e >>> 27)) + F1(a, b, c) + W[ 1]; a = ((a << 30)
| (a >>> 2));
c += ((d << 5) | (d >>> 27)) + F1(e, a, b) + W[ 2]; e = ((e << 30)
| (e >>> 2));
b += ((c << 5) | (c >>> 27)) + F1(d, e, a) + W[ 3]; d = ((d << 30)
| (d >>> 2));
a += ((b << 5) | (b >>> 27)) + F1(c, d, e) + W[ 4]; c = ((c << 30)
| (c >>> 2));
e += ((a << 5) | (a >>> 27)) + F1(b, c, d) + W[ 5]; b = ((b << 30)
| (b >>> 2));
....
this comes from Cryptix IIRC. It seems better (but less compact :) than:
for (t = 0; t < 20; t++)
{
temp = ((a << 5) | (a >>> 27)) + F1(b, c, d) + W[t];
e = d; d = c; c = ((b << 30) | (b >>> 2)); b = a; a = temp;
}
for (t = 20; t < 40; t++)
....
which is what is described in FIPS 180-1. RIPEMD-160 has the same kind
of shuffling.
As for SHA-256, whose described compression function is:
for (int i = 0; i < 64; i++) {
T1 = h + SIGMA1(e) + Ch(e, f, g) + K[i] + W[i];
T2 = SIGMA0(a) + Maj(a, b, c);
h = g;
g = f;
f = e;
e = d + T1;
d = c;
c = b;
b = a;
a = T1 + T2;
}
is there a way to convert it to the "better" form ?
So far, I have:
T1 = h + SIGMA1(e) + Ch(e, f, g) + K[0] + W[0]; T2 = SIGMA0(a) + Maj(a,
b, c); h = T1 + T2; d += T1;
T1 = g + SIGMA1(d) + Ch(d, e, f) + K[1] + W[1]; T2 = SIGMA0(h) + Maj(h,
a, b); g = T1 + T2; c += T1;
T1 = f + SIGMA1(c) + Ch(c, d, e) + K[2] + W[2]; T2 = SIGMA0(g) + Maj(g,
h, a); f = T1 + T2; b += T1;
T1 = e + SIGMA1(b) + Ch(b, c, d) + K[3] + W[3]; T2 = SIGMA0(f) + Maj(f,
g, h); e = T1 + T2; a += T1;
T1 = d + SIGMA1(a) + Ch(a, b, c) + K[4] + W[4]; T2 = SIGMA0(e) + Maj(e,
f, g); d = T1 + T2; h += T1;
T1 = c + SIGMA1(h) + Ch(h, a, b) + K[5] + W[5]; T2 = SIGMA0(d) + Maj(d,
e, f); c = T1 + T2; g += T1;
T1 = b + SIGMA1(g) + Ch(g, h, a) + K[6] + W[6]; T2 = SIGMA0(c) + Maj(c,
d, d); b = T1 + T2; f += T1;
T1 = a + SIGMA1(f) + Ch(f, g, h) + K[7] + W[7]; T2 = SIGMA0(b) + Maj(b,
c, e); a = T1 + T2; e += T1;
T1 = h + SIGMA1(e) + Ch(e, f, g) + K[8] + W[8]; T2 = SIGMA0(a) + Maj(a,
b, d); h = T1 + T2; d += T1;
....
but it does not work.
=================
Daniel L�onard (aka fork)
Computer Science Student
Universit� de Montr�al
"The nuclear warhead is one of the Humans' most efficient weapons. They
first tested it on themselves, obliterating several entire cities. The
intervening centuries since the weapon's first use had not dimmed its
effectiveness, as the Black Star proved when it blew apart. It was, from
all accounts, a most impressive display and took - by the standart of
such thing - quite some time as one section after another after another
of the ship erupted."
- Emperor Londo Mollari, Babylon 5 : In the Beginning
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Crossposted-To: comp.compression
Subject: Re: Storing an Integer on a stream
Date: Sat, 14 Oct 2000 04:14:48 GMT
SCOTT19U.ZIP_GUY wrote:
[snip fib encoding]
> >> >IIRC this encoding is asimptotically optimal.
> >>
> >> This may be asimptotically optimal for certain cases. But
> >> it is not optimal if you have a set of data and which to add
> >> a pointer to one of the data bytes my DSC program is optimal
> >> for that use.
> >> it at my site on the compression pages.
> >
> >Mr. DS, it makes no sense whatsoever to say it "may be"
> >asymptotically optimal. It either is or it isn't. In point of fact,
> >if I remember the math for fibonacci sequences correctly, for
> >increasingly large numbers, the length of this representation of a
> >number approaches a small constant (approaching 1) factor of the
> >length of the binary representation of the number.
>
> I like the wording I choose. If you don't like the wording to bad.
> Mine is a optimal encoding. Not asymptotically optimal but purely
> optimal for the job it was intended, Namely adding an integer to a
> file which represents. pointer to one the preceeding bits.
As believe I've already stated, the task in question isn't really about
describing a file length, that's merely an example of using it. The
task in question is about storing an arbitrary sized integer on a bit or
byte stream. What proof do you have that your method of storing your
integer (however you do it) is optimal?
> >Also, if the "pointer" you are talking about is in some cases a large
> >number, and in some cases a small number, then a variable length
> >representation is optimal. In your DSC program, how is the pointer
>
> I guess that means your like Mok its there to test.
The burden of proof is on you, not me. I don't have to prove that your
program is sub-optimal, you have to prove to me that it is optimal, or
at least better than all the other methods that have been suggested.
Saying I can 'test' it in no way proves that it's good, only that it
works. If it works in a sub-optimal way, I have no way of knowing.
> But in general the larger the value the longer the file will be when
> it is added to it. Like I said its optimal.
The fact that larger integers encode to longer bitstrings is true for
any variable length encoding. This does not prove, or even imply that
it is optimal. I gave 2 different variable length encoding schemes, for
which a larger value encodes to a longer bitstring, and Andras Erdei
gave a third. For each of those schemes, there is a range of integer
values for which that scheme encodes to the shortest bitstring, compared
to the others. For what range of integers does your scheme encode to be
the shortest bistring (in comparison to the others)?
> For example one may wrongly think
> that if one had a data file of 256 bytes. You might think one needs
> a file of 257 bytes. This is the maximun you need but sometimes you
> can get by with less.
Your messed up grammar makes this nearly impossible to understand. I
would *guess* you are saying that to encode the integer value 256 you
need to use 8 bits, but I'm not sure.
> >stored? As a fixed sized integer, in base 128, in base 255, using a
> >fibonacci coding, or something else? *What* the integer means isn't
> >particularly important to this discussion, but *how* it's stored on
> >the stream/in the file *is*.
>
> The way it is stored is rather complicated. ANd as sure as hell
> I will tell you wrong.
Probably, but if you don't make the attempt, noone will learn how it
works. Would you consider a fib encoding "rather complicated?" It's
certainly more complicated than the other 3 methods of writing an
integer. That doesn't, however, make it better for all cases (only ones
above a certain size, and only if you aren't worried about byte
boundaries, only bit boundaries).
> But my code is there you can test it and see for itself. Its thousands
> of C code character long.
And this is supposed to encourage me? If you didn't habitually
obfuscate your C code, perhaps I would look at what you've got.
Instead, I want you to tell me (and the rest of us on these NGs).
> Take a look if you want an example give me a set of data and I can
> give you the set with the pointer added.
Ok. Here is my data: I want to encode the pointer 3287 and send it
over a bitstream. What is the string of 0s and 1s that gets sent.
--
"Mulder, do you remember when I was missing -- that time that you
*still* insist I was being held aboard a UFO?"
"How could I forget?"
"Well, I'm beginning to wonder if maybe I wouldn't have been
better off staying abo-- I mean, wherever it was that I was
being held." [from an untitled spamfic by [EMAIL PROTECTED]]
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Looking for paper
Date: Sat, 14 Oct 2000 04:14:50 GMT
Joseph Ashwood wrote:
>
> Let me spoil the ending for you. It's an mono-alphabetic substitution.
> It is very weak, the only issue is finding the symbols, which with a
> huffman tree is not that difficult.
> Joe
It's NOT a mono-alphabetic substitution. Each symbol becomes some
number of bits, and the length of bits varies from symbol to symbol.
Consider this, take the 10,000 most used words in english. Take the 26
most commonly used words, and make that a branch, repeat a-la huffman
tree building. Assuming that at each step, the order of the A-Zs used
for the branches is randomly shuffled. So instead of a mono-alphabetic
substitution, we have a mono-dictionary substitution. By your reconing,
this should be easy to solve. Hmm! This would be an interesting
cryptosystem, anyone want to implement it?
The point is, the unknown symbol length vastly complicates things,
making it quite different from mono-alphabetic substitution.
--
"Mulder, do you remember when I was missing -- that time that you
*still* insist I was being held aboard a UFO?"
"How could I forget?"
"Well, I'm beginning to wonder if maybe I wouldn't have been
better off staying abo-- I mean, wherever it was that I was
being held." [from an untitled spamfic by [EMAIL PROTECTED]]
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Looking for paper
Date: Sat, 14 Oct 2000 04:14:54 GMT
John A. Malley wrote:
>
> Benjamin Goldberg wrote:
> >
> > I recall seeing a paper where data was compressed using a static
> > huffman tree (with 0 and 1 labels on the branches randomly swapped),
> > and the tree hidden... and analysis was done to attempt to recover
> > the tree. I don't, however, recall *where* I saw the paper... I
> > think it was a .ps, or .ps.gz, not a .pdf or .html document.
> >
>
> Perhaps it's the Master's Thesis from Mojdeh Mohtashemi, "On the
> Cryptanalysis of Huffman Codes" June, 1992, at:
>
> http://theory.lcs.mit.edu/~cis/theses/mohtashemi-masters.ps
Yup, that's exactly the title I was looking for! Thanks, that helps.
BTW, has he ever posted here?
--
"Mulder, do you remember when I was missing -- that time that you
*still* insist I was being held aboard a UFO?"
"How could I forget?"
"Well, I'm beginning to wonder if maybe I wouldn't have been
better off staying abo-- I mean, wherever it was that I was
being held." [from an untitled spamfic by [EMAIL PROTECTED]]
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Possible secure CRC using shrinking?
Date: Sat, 14 Oct 2000 04:15:01 GMT
Scott Fluhrer wrote:
>
> Benjamin Goldberg <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > I don't know how good this idea is, so I'd like some comments...
> >
> > First, take you data, and compute the CRC of it. Then, using the
> > same polynomial as the CRC used, use the CRC as the seed of a
> > self-shrinking LFSR. For an N bit CRC, discard 2N bits from the
> > SSLFSR, then output the next N bits. Is this a secure hash?
>
> If I understand you right, you compute a CRC on the data, and then
> output a function of that CRC. If that's the case, it's not a secure
> hash -- it's trivial to find collisions on the original CRC.
Ack, yes, you're right. How about, if after every block, we move the
CRC state toe the SSLFSR, the discard some bits, then move it back into
the CRC? In fact, if we process *less-than* N bits of data for each
time we put it through the SSLFSR, it should be difficult or impossible
to find collisions, anywhere along the route. So, for a 256 bit
polynomial, we process 31 bytes, then do self-shrinking for some number
of cycles, then the next 31 bytes, etc. and finally discard 512 ss lfsr
bits, and lastly output 256 sslfsr bits.
--
"Mulder, do you remember when I was missing -- that time that you
*still* insist I was being held aboard a UFO?"
"How could I forget?"
"Well, I'm beginning to wonder if maybe I wouldn't have been
better off staying abo-- I mean, wherever it was that I was
being held." [from an untitled spamfic by [EMAIL PROTECTED]]
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: The science of secrecy: Simple Substition cipher
Date: Sat, 14 Oct 2000 04:15:09 GMT
Miki Watts wrote:
>
> > Dear group,
> > Channel 4 (UK) are running a series of 'The science of secrecy'
> > and after the show mentioned a cipher competition on thier website
> > www.channel4.co.uk/nextstep. The message uses a substition cipher
> > where the letters are pared
> > ie if cT 'A' = pT 'T'
> > then cT 'T' = pT 'A'.
> >
> > The problem is i cant make sense of the last line.
> > Can anyone help?
> >
> > -TIA-
> >
> > Cipher:
> > Iroho awg genoirtms tm iro iemo
> > ez irtg meio irwi swko no showi
> > jmowgtmogg. (Poiioh 'P')
> > 'Iro Sepx Qjs' qc O.W. Leo
> >
> >
> > Plaintext:
> > There was something in the tone
> > of this note that gave me great
> > uneasiness. (Letter 'L')
> > ????????????????????????????
>
> Deciphering what i can:
>
> 'The gol? ?ug' ?? E.A. ?oe
>
> I'd say: "The gold bug" E.A. Poe
Don't you mean: "The gold bug" by E.A. Poe
(you dropped the word "by")
One thing I would note, is that because the substitution is (as stated
in the start of the thread) an involution, the fact that P maps to L
(from Poiioh->Letter), you should also know that L maps to P. This
means that the first letter of Poe did not have to be guessed, it should
have been known.
--
"Mulder, do you remember when I was missing -- that time that you
*still* insist I was being held aboard a UFO?"
"How could I forget?"
"Well, I'm beginning to wonder if maybe I wouldn't have been
better off staying abo-- I mean, wherever it was that I was
being held." [from an untitled spamfic by [EMAIL PROTECTED]]
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: working with huge numbers
Date: Sat, 14 Oct 2000 04:15:17 GMT
Ray Dillinger wrote:
>
> Eric Young <[EMAIL PROTECTED]> wrote:
>
> : Well, in my case I originally wrote my bignum library specifically
> : to learn how to do large number division. I was intimidated by it,
> : so I took it as a challenge to learn how it was done :-).
>
> When I'm learning a new language, one of the first things I always
> write is a bignum library. I don't go for ultimate efficiency
> with it though; I just toss it together and make sure it works
> correctly.
>
> Using such libraries for crypto has not really been a problem
> at all; Okay, my modular exponentiation routine may take three
> or four eyeblinks instead of one -- but I don't really care
> because encryption/decryption tends to be quite fast, measured
> in human terms, anyway. So I don't deal with the machine code
> and hand-tweak processor scheduling and carefully arrange blocks
> to fit into the cache on particular CPUs (all of which techniques
> I see in the PGP code), I just write numerical algorithms on 16-
> bit and 32-bit integers. They are efficient *algorithms*,
> so they run in the "right" order of magnitude -- but chasing down
> every last bit of performance available is just not worth my time
> or the trouble of verifying the resulting assembly-language code.
When you do multiplications, do you use Montgomery form? This isn't
merely a little tweak that gets a tiny increase in performance, it is a
major speed-up. Also, I believe that there's some kind of way to use
Fourier transforms to get large speed increases (not sure on this,
though). In other words, do you use the most efficient algorithms, or
the easiest to code? Also, for exponentiation, there's a method that
works using repeated squaring, and squaring a big integer can be faster
than multiplying it by itself.
> If the task were cryptanalysis, or brute-force trying of keys,
> then sure, it would be time to work over the bignum library
> with a fine-toothed comb and bum it into a state of high
> perfection. But generally, cryptography (which is a much simpler
> task than cryptanalysis) is fine with simple straightforward,
> general implementations. And it makes the code ten times easier
> to verify as correct.
I agree, sort of, but I think that using a pre-written library is even
better for verifying your code is correct, if you are able to assume
that the library is correct.
--
"Mulder, do you remember when I was missing -- that time that you
*still* insist I was being held aboard a UFO?"
"How could I forget?"
"Well, I'm beginning to wonder if maybe I wouldn't have been
better off staying abo-- I mean, wherever it was that I was
being held." [from an untitled spamfic by [EMAIL PROTECTED]]
------------------------------
From: Greggy <[EMAIL PROTECTED]>
Subject: Re: Why trust root CAs ?
Date: Sat, 14 Oct 2000 04:52:10 GMT
In article <[EMAIL PROTECTED]>,
Doug Kuhlman <[EMAIL PROTECTED]> wrote:
>
>
> Greggy wrote:
> >
> >
> > I don't see why the banks just produce their own certificates and
> > publicly state their public key in the news papers, WSJ, etc. Then
> > there is no CA and you are absolutely certain that your bank is
> > providing the security they need to CTA with...
> >
> Oh, that'd be fun! Why should I trust the newspaper. It'd be much
> easier for "Joe's Discount Hacking Service" to run a few dozen
> fraudulant postings of public keys than to go through the trouble of
> spoofing a business, wouldn't it? Why would you trust your newspaper
> (or WSJ or ...) if you don't trust a CA who at least tries to verify
the
> entity involved?
That's silly. If Bank of America posted their key in the WSJ and it
was not accurate, don't you think that the bank would shut down their
servers until the public were told the truth?
That is far more secure than hoping a CA did his job right and did not
take a bribe. Far more secure.
--
If I were a cop, I would refuse to go on any no knock raid.
But then, I am not a cop for basically the same reasons.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
** 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
******************************
