Cryptography-Digest Digest #403, Volume #13 Sat, 30 Dec 00 13:13:01 EST
Contents:
SHA Padding (George)
Re: SHA Padding (Francois Grieu)
Re: calculating 2048 bit public key ops with an 1024 bit engine? (Francois Grieu)
One Way Hash Functions (Nemo psj)
Re: CPRM, Intel's big xmas joke of protected media (Nemo psj)
Re: "Content Protection for Recordable Media" (Nemo psj)
Re: which algorithm ("infinito.it")
Re: SHA Padding (Stephan T. Lavavej)
Re: A Censorship Resistant Digital Magazine Scheme (John Bailey)
Re: A Censorship Resistant Digital Magazine Scheme (David A Molnar)
Re: One Way Hash Functions (David A Molnar)
Re: One Way Hash Functions (Nemo psj)
Re: Are there any known typos in the Jones, Sato Wada & Wiens Explicit Polynomial
for Primes as appears in P. Ribenboim's books? (Steve Roberts)
Re: Are there any known typos in the Jones, Sato Wada & Wiens Explicit Polynomial
for Primes as appears in P. Ribenboim's books? (Benjamin Goldberg)
Re: CPRM, Intel's big xmas joke of protected media (nobody)
Re: Are there any known typos in the Jones, Sato Wada & Wiens (Mok-Kong Shen)
Proving Associativity for Elliptic Curves ("Martin Hamann")
----------------------------------------------------------------------------
From: George <[EMAIL PROTECTED]>
Subject: SHA Padding
Reply-To: [EMAIL PROTECTED]
Date: Sat, 30 Dec 2000 1:03:31 -0600
I'm having trouble assigning a 64-bit value to the last block of data to be
processed. I have coded my program to pad the data until the last 64 bits of
data are reached. I'm having trouble storing the 64 bit message length into
the character array, which can hold no more than 8 bits at a time. Could
someone please give me some suggestions? Here's what I tried (to fill the
last 4 bytes):
msg[N*64+60] = len >> 24;
msg[N*64+61] = (len << 8) >> 24;
msg[N*64+61] = (len << 16) >> 24;
msg[N*64+61] = (len << 24) >> 24;
msg[(N+1)*64] = '\0';
-George
[EMAIL PROTECTED]
------------------------------
From: Francois Grieu <[EMAIL PROTECTED]>
Subject: Re: SHA Padding
Date: Sat, 30 Dec 2000 09:51:36 +0100
[EMAIL PROTECTED] is coding SHA (hopefully: SHA1) and has
> trouble assigning a 64-bit value to the last block of data"
1> msg[N*64+60] = len >> 24;
2> msg[N*64+61] = (len << 8) >> 24;
3> msg[N*64+61] = (len << 16) >> 24;
4> msg[N*64+61] = (len << 24) >> 24;
5> msg[(N+1)*64] = '\0';
several problems here:
- in line 3 and 4, the offsets should be 62 and 63.
- the length should be in the last 8 octet (byte), not 4.
- line 5 is terrible: the message must be considered an array
of bytes, not a 0 terminated string; the later simply can not work.
- the code assumes len is a 32 bit variable; a more portable technique
would be
msg[N*64+56] = msg[N*64+57] = msg[N*64+58] = msg[N*64+59] = 0;
msg[N*64+60] = (len>>24)&255;
msg[N*64+61] = (len>>16)&255;
msg[N*64+62] = (len>> 8)&255;
msg[N*64+63] = (len )&255;
- len is the bit length on 32 bit; therefore the longest message the
code can handle is below 512 M byte, not enough for a full CD-ROM.
- code that performs computation of N, bit padding (for a message
multiple of 8 bits: appending a final 0x80), and zeroes filling,
is not shown; it is notoriously hard to get right.
Francois Grieu
------------------------------
From: Francois Grieu <[EMAIL PROTECTED]>
Crossposted-To: sci.math.num-analysis
Subject: Re: calculating 2048 bit public key ops with an 1024 bit engine?
Date: Sat, 30 Dec 2000 10:33:11 +0100
"Joseph Ashwood" <[EMAIL PROTECTED]> wrote:
>"Aki M Suihkonen" <[EMAIL PROTECTED]> wrote:
>> Given a crypto core capable of performing upto 1024 bit wide
>> (public key) modular exponentiation, is it even relatively easy
>> to extend it for operations twice the length?
> just use the same multiplication techniques many of us learned
> in grade school, but use base-2^512 numbers instead of base-10.
> That will give you the multiplication, and exponentiation is a
> simple extention. It'll take a bit more code than a 1024-bit
> exponentiation, but it'll work.
The problem comes with modular reduction. The grade school algorithm
is to guess the quotient digit after digit. Guessing a digit is
workable in base 10, but in base 2^512...
One technique is to compute an approximate inverse of N,
say Q = 2^2560/N which is a 513 bit number (assuming N is 2048 bits);
this can be done using an iterative method involving only
multiplication. Then quotient estimation can be performed by one
multiplication by Q (or by the low 512 bits of Q followed by one
addition).
All the above use the 1024 bit engine as a 512 bit exact multiplier;
this is possible by using a dummy modulus like 2^1024-1.
I am unaware of any technique that can resuse the modular exponentiation
as a black box and double the modulus width; I even wonder if the modular
reduction can be reused at all, unless the quotient is also available.
Francois Grieu
------------------------------
From: [EMAIL PROTECTED] (Nemo psj)
Date: 30 Dec 2000 09:41:36 GMT
Subject: One Way Hash Functions
Well you guys are the xperts on this stuff so I'll post here, I have heard of
MD5 and it was said to be a one way hash function, then I heard it really
wasn't. So no I'm all flusterd and since the Barns and Noble near me dont like
me very mush (long storie) could any of you point out where I can get some info
on One way Hash functions and or source or mathematicle epxlanations.
-Jay King
------------------------------
From: [EMAIL PROTECTED] (Nemo psj)
Date: 30 Dec 2000 10:09:49 GMT
Subject: Re: CPRM, Intel's big xmas joke of protected media
Mail your email address at [EMAIL PROTECTED] and ill send you everything ;P
------------------------------
From: [EMAIL PROTECTED] (Nemo psj)
Date: 30 Dec 2000 10:27:31 GMT
Subject: Re: "Content Protection for Recordable Media"
Can we all say psycho!
This is Bullshit, and will go down in flames all the rest of the crack pot
ideas the media industries come up with.
------------------------------
From: "infinito.it" <[EMAIL PROTECTED]>
Subject: Re: which algorithm
Date: Sat, 30 Dec 2000 11:29:31 -0800
"David Schwartz" <[EMAIL PROTECTED]> wrote:
> Carl Egil Monstad wrote:
> >
> > I have one single line of ciphertext.
> > Does anybody know how I can find out which algorithm is used?
>
> Ideally, ciphertext should look entirely random to someone who doesn't
> know they key. Since you don't know the key, if a good cipher was
> chosen, the output should be indistinguishable from random. So there
> would be no information from which you could divine the algorithm. On
> the otherhand, if the algorithm is weak (say, simple substitution) it
> will leave clues to that in the output, which will resemble the input in
> subtle ways.
I have been reading Helen Fouch� Gaines' "CRYPTANALYSIS, a study of ciphers
and their solutions" for a while and I have discovered clean and clever ways
to look at short messages using now-weak algorithms.
She is concentrating on classic ciphers (the first edition is dated 1939),
but she is very good at underlining different approaches that can lead us to
great discoveries. Some methods that are particularly good at breaking
"aristocrats" can be used for testing and achieving lots of information,
even from very very short messages.
Aristocrats are messages such as those you find in the papers and that have
been written to be attacked by people with no technical background.
Mr Ohaver, an expert she is talking of, suggested interesting ways to find
the plain text entropy you would like to know. I think that her book could
be a great
starting point if you suspect that there might be a classic cipher behind
the worm you have got.
Happy reading!
Alberto Vassena
mailto:[EMAIL PROTECTED]
http://members.tripod.com/avx
------------------------------
From: stl/*This_is_a_comment*[EMAIL PROTECTED] (Stephan T. Lavavej)
Subject: Re: SHA Padding
Date: Sat, 30 Dec 2000 12:01:13 GMT
The very first (and so far, the only) C program I have written was an
implementation of SHA-1. After many, many versions, I believe I got
everything exactly right, and have achieved full compliance (this was
notoriously hard to do, especially for huge files). My code, I like
to think, is clean, because I'm not good enough yet to make it
complicated, and should be fully ANSI C99 compliant. The program is
GPL'ed and available on my website. The padding was indeed difficult
to do; originally I wrote a tempfile and padded it (incorrectly). Now
I use a function that sucks bits out of the file, and when the file is
finished, supplies the necessary padding bits, without the calling
function ever having to know the difference. Perhaps my code can help
you to improve yours.
-*---*-------
Stephan T. Lavavej
http://quote.cjb.net
stl/*This_is_a_comment*[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (John Bailey)
Crossposted-To: alt.cypherpunks
Subject: Re: A Censorship Resistant Digital Magazine Scheme
Date: Sat, 30 Dec 2000 11:01:40 GMT
On Sat, 30 Dec 2000 01:12:28 GMT, [EMAIL PROTECTED] (George
Weinberg) wrote:
>A Censorship Resistant Digital Magazine Scheme
>
> The system I have in mind assumes that one wants to publish
>something
>like a psudonymously authored magazine, that is, that it has
>sequential
>issues (although not necessarily any fixed publishing schedule).
(snipped)
> The key is a one-way function. Although I may refer to the
>magazine as
>"Rabid", its "real" name is some horrible 256 bit number followed by
>",0."
>I'll call that horrible number H0.
>When I want to publish issue 1, its name is the same awful number
>followed
>by ",1". The system has a predefined 256 bit hash function
>which we'll call H(). The file will have some header that will get
>stripped
>away before it gets stored on the system, which will contain some
>other 256 bit number which I'll call H1. H(H1) = H0. Future issues
>will be similarly named with similar numbers, H(H(H(H3))) = H0 and so
>on.
(snipped)
>
>Comments? Suggestions?
>
>Thnaks,
> George Weinberg
>
Just scanning your scheme for broad concept, two comparisons come to
mind.
http://theory.lcs.mit.edu/~rivest/chaffing.txt
http://www.cl.cam.ac.uk/~fms27/cocaine/
John
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Crossposted-To: alt.cypherpunks
Subject: Re: A Censorship Resistant Digital Magazine Scheme
Date: 30 Dec 2000 11:17:47 GMT
John Bailey <[EMAIL PROTECTED]> wrote:
[snip setup]
>>away before it gets stored on the system, which will contain some
>>other 256 bit number which I'll call H1. H(H1) = H0. Future issues
>>will be similarly named with similar numbers, H(H(H(H3))) = H0 and so
>>on.
> (snipped)
>>
>>Comments? Suggestions?
>>
>>Thnaks,
>> George Weinberg
>>
> Just scanning your scheme for broad concept, two comparisons come to
> mind.
> http://theory.lcs.mit.edu/~rivest/chaffing.txt
> http://www.cl.cam.ac.uk/~fms27/cocaine/
slightly less broadly, this seems to be related to "one-time signatures."
These are mentioned in the _Handbook of Applied Cryptography_
http://www.cacr.math.uwaterloo.ca/hac/
chapter 11 is the chapter to look at.
Also see Bleichenbacher and Maurer
Optimal Tree-based One-time Digital Signature Schemes
http://citeseer.nj.nec.com/bleichenbacher-optimal.html
-David
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: One Way Hash Functions
Date: 30 Dec 2000 11:19:22 GMT
Nemo psj <[EMAIL PROTECTED]> wrote:
> Well you guys are the xperts on this stuff so I'll post here, I have heard of
> MD5 and it was said to be a one way hash function, then I heard it really
> wasn't. So no I'm all flusterd and since the Barns and Noble near me dont like
> me very mush (long storie) could any of you point out where I can get some info
> on One way Hash functions and or source or mathematicle epxlanations.
The MD5 I'm familiar with is a one-way hash function. Maybe you heard
about something else which used MD5 as a component?
A good place to look for info is the _Handbook of Applied Cryptography_
http://www.cacr.math.uwaterloo.ca/hac/
free download. no Barnes & Noble needed.
-David
------------------------------
From: [EMAIL PROTECTED] (Nemo psj)
Date: 30 Dec 2000 11:36:10 GMT
Subject: Re: One Way Hash Functions
Thank you, wow I looked at my typing it was bad. Oh well it's what I get for
typing at 6AM, Im watching this post on the otherhand.
Again Thanks for the Info I had that book in PDF format once but i formatted!
------------------------------
From: [EMAIL PROTECTED] (Steve Roberts)
Subject: Re: Are there any known typos in the Jones, Sato Wada & Wiens Explicit
Polynomial for Primes as appears in P. Ribenboim's books?
Date: Sat, 30 Dec 2000 12:40:16 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
>
>"John A. Malley" wrote:
>
>[snip]
>>
>> When I look at the polynomial I don't see how it ever generates a
>> positive value. (Put off coding it until I clear this question up
>> first.) The polynomial is shown as two terms multiplied together, and
>> leaving most details out, looks like
>>
>> (k+2) * { 1 - [...]^2 - [...]^2 - ... [...]^2 }
>>
>> ^^^^ ^^^^^^^^
>> left term right term
>>
>
>I have seen the formula in the book but have never used
>it. I conjecture that your 'the 26 unknowns range in the
>set of non-negative integers' doesn't apply. For it says
>only that a,b,c,.... z are indeterminates and there is
>no explicit mention that these should be non-negative.
>
>It would be interesting to know your experience with
>the formula, for I had the (subjective) impression till
>now that it might not be very practical.
>
>M. K. Shen
I spent a day with the formula too - apart from it appearing to
require enormous values of the coefficients to get beyond the simple
primes like 3 5 and 7, I could not understand how it could work
because of the above squaring problem - and the factor (k+2) which
means that any result must be composite anyway. However a formula
for generating primes would be pretty remarkable, if if were any use
at all.
Steve Roberts
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Are there any known typos in the Jones, Sato Wada & Wiens Explicit
Polynomial for Primes as appears in P. Ribenboim's books?
Date: Sat, 30 Dec 2000 12:49:10 GMT
Steve Roberts wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
> >
> >
> >"John A. Malley" wrote:
> >
> >[snip]
> >>
> >> When I look at the polynomial I don't see how it ever generates a
> >> positive value. (Put off coding it until I clear this question up
> >> first.) The polynomial is shown as two terms multiplied together,
> >> and leaving most details out, looks like
> >>
> >> (k+2) * { 1 - [...]^2 - [...]^2 - ... [...]^2 }
> >>
> >> ^^^^ ^^^^^^^^
> >> left term right term
> >>
> >
> >I have seen the formula in the book but have never used
> >it. I conjecture that your 'the 26 unknowns range in the
> >set of non-negative integers' doesn't apply. For it says
> >only that a,b,c,.... z are indeterminates and there is
> >no explicit mention that these should be non-negative.
> >
> >It would be interesting to know your experience with
> >the formula, for I had the (subjective) impression till
> >now that it might not be very practical.
> >
> >M. K. Shen
>
> I spent a day with the formula too - apart from it appearing to
> require enormous values of the coefficients to get beyond the simple
> primes like 3 5 and 7, I could not understand how it could work
> because of the above squaring problem - and the factor (k+2) which
> means that any result must be composite anyway. However a formula
> for generating primes would be pretty remarkable, if if were any use
> at all.
>
> Steve Roberts
Considering the number of coefficients, and the magnitude of the values
those coefficients must be for the formulae to work, it's probably
infeasible/impossible to use conventional methods to find reasonalby
sized values for which this formula works. However, I wonder if quantum
computing might be a possible solution, once we have enough qbits, that
is.
--
Power interrupts. Uninterruptable power interrupts absolutely.
[Stolen from Vincent Seifert's web page]
------------------------------
From: nobody <[EMAIL PROTECTED]>
Subject: Re: CPRM, Intel's big xmas joke of protected media
Date: Sat, 30 Dec 2000 15:09:35 +0000
>Mail your email address at [EMAIL PROTECTED] and ill send you everything ;P
if you have the other docs, why not post them here. a lot of ppl would
be interested in reading them.
--
pel
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Are there any known typos in the Jones, Sato Wada & Wiens
Date: Sat, 30 Dec 2000 18:43:37 +0100
Steve Roberts wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
> >"John A. Malley" wrote:
> >
> >[snip]
> >>
> >> When I look at the polynomial I don't see how it ever generates a
> >> positive value. (Put off coding it until I clear this question up
> >> first.) The polynomial is shown as two terms multiplied together, and
> >> leaving most details out, looks like
> >>
> >> (k+2) * { 1 - [...]^2 - [...]^2 - ... [...]^2 }
> >>
> >> ^^^^ ^^^^^^^^
> >> left term right term
> >>
> >
> >I have seen the formula in the book but have never used
> >it. I conjecture that your 'the 26 unknowns range in the
> >set of non-negative integers' doesn't apply. For it says
> >only that a,b,c,.... z are indeterminates and there is
> >no explicit mention that these should be non-negative.
> >
> >It would be interesting to know your experience with
> >the formula, for I had the (subjective) impression till
> >now that it might not be very practical.
>
> I spent a day with the formula too - apart from it appearing to
> require enormous values of the coefficients to get beyond the simple
> primes like 3 5 and 7, I could not understand how it could work
> because of the above squaring problem - and the factor (k+2) which
> means that any result must be composite anyway. However a formula
> for generating primes would be pretty remarkable, if if were any use
> at all.
Sorry, I made a blunder. The book indeed says that the
variables are non-negative. There is one interpretation
that can not be excluded in my view (this would mean that
there is no typo): One has to find a set of values for
the 26 varaibles such that each of the [...] is zero. A
value of k in such a set then would render k+2 be a prime.
The formula apparently would generate primes with high
degree of repetitions and hence be of no practical use
as a scheme to generate primes of non-trivial size.
M. K. Shen
------------------------------
From: "Martin Hamann" <[EMAIL PROTECTED]>
Subject: Proving Associativity for Elliptic Curves
Date: Sat, 30 Dec 2000 19:04:34 +0100
Reply-To: "Martin Hamann" <[EMAIL PROTECTED]>
In elliptic curve cryptography, points on elliptic curve together with
addition form a group with identify element O (where O is the point at
infinity)
I'm trying to prove that this is truly a group. In my beloved
"Cryptography - Theory and Practice" by D. Stinson, on page 184 he states:
"[...] but proving associativity is quite difficult"
Can anybody enlighten me as to why it is difficult ? Is it the special cases
when adding to points which are equal or only differ in sign on the
y-coordinate ? Or is there another thing I haven't seen ?
Are there any places on the net or in the books, where the proof is given ?
;-)
Thanks in advance
Martin Hamann, Student,
Technical University of Denmark.
http://www.dtu.dk
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
