Cryptography-Digest Digest #260, Volume #14 Sat, 28 Apr 01 20:13:00 EDT
Contents:
Re: speeding up exponentiation ("Tom St Denis")
Re: Secure Digital Music Initiative cracked? (David A Molnar)
Re: Censorship Threat at Information Hiding Workshop (Mok-Kong Shen)
Re: speeding up exponentiation (John Savard)
Re: Combining two plaintexts into ciphertext (John Savard)
Re: speeding up exponentiation ("Tom St Denis")
Re: speeding up exponentiation (Quisquater)
cRYPTO cHALLENGE ("cubeet")
Re: Shortcut ElGamal (Mark Wooding)
Re: cRYPTO cHALLENGE (Carsten Saager)
Re: What Is the Quality of Randomness? ("Trevor L. Jackson, III")
Re: Secure Digital Music Initiative cracked? (David Wagner)
Re: Secure Digital Music Initiative cracked? (Marc)
Re: ancient secret writing (newbie)
Re: SHA PRNG (Tim Tyler)
Re: RC4 Source Code (Bill Unruh)
Re: Running Time of Factoring Algorithms (Bill Unruh)
Re: Censorship Threat at Information Hiding Workshop (Xcott Craver)
Re: SHA PRNG ("Tom St Denis")
----------------------------------------------------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: speeding up exponentiation
Date: Sat, 28 Apr 2001 10:26:24 GMT
=====BEGIN PGP SIGNED MESSAGE=====
Hash: SHA1
"Paul Rubin" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> "Tom St Denis" <[EMAIL PROTECTED]> writes:
> > I was think of a nice way to speed up exponentiation in Z*p some.
> >
> >
> > Basically my idea is that at some level g^x can be expressed as
> > g^(z+y) = (g^z)(g^y) where x = z + y. Let's say you have a
> > 256-bit exponent (as in the case of DSA right or is it bigger?)
> > anyways... you do a series of tables say 8-bits wide on the
> > input....
>
> Yes, there are a whole lot of precomputation hacks like this. See
> for example Brickell et al's paper in Eurocrypt 92(?).
Their method is O(log log N) on O(log N / log log N) processors. My
idea is for a single processor.
Tom
=====BEGIN PGP SIGNATURE=====
Version: PGPfreeware 7.0.3 for non-commercial use <http://www.pgp.com>
Comment: Key at: http://tomstdenis.home.dhs.org/key.asc
iQA/AwUBOuqazwULrT+pXe8cEQKk4wCdHC37MuE37iDJALXRWwifwdFRwgEAn2RR
R33eRBiw6+kuZTN0TnHQNpr/
=lHPy
=====END PGP SIGNATURE=====
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Secure Digital Music Initiative cracked?
Date: 28 Apr 2001 10:47:48 GMT
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
> David A Molnar wrote:
>> ... It still shocks me that the RIAA can do what the NSA did not -
>> prevent a paper from being presented at a public conference.
> Actually the paper you're thinking of was the subject of personal
> attention by an NSA employee working outside the proper scope of
> his duties, and the Agency didn't back him up. But anyway, the
OK. Thanks for the clarification!
> big difference is that Congress passed that stupid unconstitutional
> law, which the SDMI lawyers can wave as a big threatening stick.
Yes. Maybe this will lead to a change in the law...
-David
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Censorship Threat at Information Hiding Workshop
Date: Sat, 28 Apr 2001 13:15:58 +0200
"Trevor L. Jackson, III" wrote:
>
> Mok-Kong Shen wrote:
>
> > "Trevor L. Jackson, III" wrote:
> > >
> > > In most jurisdictions your friend _can_ sign your signature and have it
> > > upheld as valid in court if you direct him to do so and, of course, testify
> > > to that effect.
> >
> > We were discussing anyway in the context of cards. How can
> > one 'sign my signature' and do it in a way that is
> > the same as mine (my signature will be verified with that
> > on the card by the transaction partner), unless perhaps
> > he is a professional 'faker' of signatures? I can sign a
> > special document authorizing someone to take money from
> > my bank account etc., but then he is employing his own
> > signature in such actions, isn't it?
>
> The key concept is that the signature was created "by direction". In the
> military a commanding officer is required to execute certain documents. He may
> delegate that action to a subordinate who executes the CO's signature. I think
> the fully elaborated form is "<required signature> by direction, <signer's
> signature>", or something similar.
>
> If the authorized person directs someone to sign for them then the resulting
> (indirect) signature has all of the authority of an original (direct) signature.
> In some places married couples can use this convention for each other's signature
> even in the absence of an immediate directive.
Yes. But that doesn't change the fact my friend signs
'his', not 'my' signature. The situation you described
is quite common. If I am on vacation and my colleage
(of lower position) who represents me in that time period
signs a document that is normally exclusively to be done
by me, he can sign but has to put a remark to the effect
that he is signing in his position as my representative.
Now returning to the context of cards, the transaction
partner sees my signature on the card which is different
from that of my friend. He wouldn't accept his signature
(unless maybe he can produce a document bearing my signature
showing my authorization).
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: speeding up exponentiation
Date: Sat, 28 Apr 2001 11:34:15 GMT
On Sat, 28 Apr 2001 10:26:24 GMT, "Tom St Denis"
<[EMAIL PROTECTED]> wrote, in part:
>Their method is O(log log N) on O(log N / log log N) processors. My
>idea is for a single processor.
The standard method for raising a number to a really high power is
similar to what you've outlined.
In most RSA implementations, the calculation m^e mod P is carried out
by first calculating m^2, m^4, m^8, m^16... by repeated squarings
(each one requiring only a multiplication mod P) and then multiplying
together the powers of m corresponding to 1 bits in the binary
representation of e.
If it weren't for this, RSA and Diffie-Hellman public-key systems
would not be practical.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Combining two plaintexts into ciphertext
Date: Sat, 28 Apr 2001 11:47:16 GMT
On Sat, 28 Apr 2001 07:22:45 GMT, Ken Savage <[EMAIL PROTECTED]>
wrote, in part:
>I figure that two 8-bit quantities can be concatenated together to
>yield a 16-bit quantity --- a crude form of combining. However, a
>more sophisticated form could combine them into a 16-bit value with
>the added benefit of come cryptographic security. And for those
>times that the mathematics of combining won't work, by peppering
>in some error-correction codes, we can recover the plaintexts.
Well, using a method involving error correction certainly raises some
interesting possibilities, because then the two messages are allowed
to overlap.
By using larger chunks, there are more possible ways to conceal the
other message after one message is revealed.
One of the big problems is that, since both messages can be recovered
independently, the content of the other message, say in encrypted
form, can't be used to vary how a message is encrypted - except within
stages where _both_ messages can be decrypted to an equal extent, or
where one message is encrypted to a greater extent than the other.
That's because you can't have a system where the final, encrypted form
of each message changes the encryption of the other message from the
beginning, because then neither message can be encrypted: each one
depends on the other one being encrypted first.
So if one needs a 128-bit block size to make the possibilities
interesting enough for a single message, one should combine two
messages into 256-bit blocks, because the important part of the
encryption has to be done for each message on its own.
Of course, one could still take two *encrypted* messages, and mix the
bytes of them into 16-bit chunks. But then the rule for combining them
should at least change from one 16-bit unit to the next, making it a
stream cipher.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: speeding up exponentiation
Date: Sat, 28 Apr 2001 11:49:01 GMT
"John Savard" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> On Sat, 28 Apr 2001 10:26:24 GMT, "Tom St Denis"
> <[EMAIL PROTECTED]> wrote, in part:
>
> >Their method is O(log log N) on O(log N / log log N) processors. My
> >idea is for a single processor.
>
> The standard method for raising a number to a really high power is
> similar to what you've outlined.
>
> In most RSA implementations, the calculation m^e mod P is carried out
> by first calculating m^2, m^4, m^8, m^16... by repeated squarings
> (each one requiring only a multiplication mod P) and then multiplying
> together the powers of m corresponding to 1 bits in the binary
> representation of e.
>
> If it weren't for this, RSA and Diffie-Hellman public-key systems
> would not be practical.
I know of the multiply-and-square method. My idea is to precompute as much
as possible.
Tom
------------------------------
From: Quisquater <[EMAIL PROTECTED]>
Subject: Re: speeding up exponentiation
Date: Sat, 28 Apr 2001 14:27:01 +0200
Well-known remarks. In order to introduce you (and others) in the field,
read the following paper:
A survey of fast exponentiation methods (1998) (Correct)
Daniel M. Gordon, J. Algorithms
http://citeseer.nj.nec.com/gordon98survey.html
(especially the section 5).
This paper is nearly up-to-date.
See also
Secure acceleration of DSS signatures using insecure server
Philippe B'eguin and Jean-Jacques Quisquater
http://citeseer.nj.nec.com/231594.html
Jean-Jacques Quisquater,
------------------------------
From: "cubeet" <[EMAIL PROTECTED]>
Subject: cRYPTO cHALLENGE
Date: Sat, 28 Apr 2001 22:28:05 +1000
A rather interesting crypto to play with, well food for though really.
Happy playing with it.
TQHYP WQZYP RYCCA YFRAB SGOTK UUSKY KAVQK WNUKQ ZUQJB HHGDE RTVYJ TITVQ
QIAMU FNZGR OWDUQ PIOAN KBVZV ESFLU GPRGD GAZFG LHXPT UEQPX JDERH YABXJ
VLYNG RCEHQ AUKGY AGSRI RWJRA FWHEZ QNAGX LESQX JPRWT WYFWS HSCAA VOCWZ
RYYGN IWOEZ QXOVL OAOFI JSRWG PBEAJ NAFYU GITZO UINEM CQNFX BTOEF UXIWB
LPLHD HEGIR DVHSV VTJDY GLYGR SGHZN VXTHY JXYZW ELKFW RCAJH NVEAQ BNIYP
LPUTQ FWUPI DLMXY JWQLU WPINZ CMUCT STATG QXBGS RLHTT UQLDD QTIFU KOZXK
HBKRC ZAOHC WTVCX NULNC ICTBL YBTET RXJQW RONKU WBOEQ OSFLY QBIEY VRLVB
UCUBK CFSSK JKILF LCGPU MKIAW DINAT SEVSY FDUXR GHSCE EQOQM OTJMX AHDBG
IVHPV RWNIX MFDFJ HGPZU KFTHH PGNZM CZXAQ SLPMG ZORIO GXCFE RHUFI OYRFY
HMSQV AUYXT DPQVT YNBBR XRYIS MGPCD VKKUJ MJCDZ AAIZC P
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Shortcut ElGamal
Date: 28 Apr 2001 14:26:47 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Just trying to figure this out. In DSA you pick a large prime p
> (1024 bits etc..) such that p-1/2 has a large prime factor q (of at
> least 512 bits) and such that g is a generator for the subgroup Z*q
> of Z*p. (Is that remotely right?)
in DSA, q is 160 bits. Increasing this is pointless unless you also
increase the size of p.
> This is such that one can use log2(q) bit exponents and speed up the
> computations (i.e signatures).
>
> Can't this trick also be used for ElGamal encryption?
Of course. It won't make the ciphertexts any smaller, though.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Carsten Saager)
Subject: Re: cRYPTO cHALLENGE
Date: 28 Apr 2001 15:17:16 GMT
"cubeet" <[EMAIL PROTECTED]> wrote in
<auyG6.13357$[EMAIL PROTECTED]>:
> A rather interesting crypto to play with, well food for though really.
> Happy playing with it.
>
We have already a discussion about solving this puzzle on rec.puzzles->
Re: Codebreaker puzzle at 'The Register'
This is a contest at http://www.theregister.co.uk The fastest puzzle-
solvers will receive a bokk and some tickets for Bletchley Park. So far it
seems that nobody has managed to break it.
Carsten
------------------------------
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: What Is the Quality of Randomness?
Date: Sat, 28 Apr 2001 16:04:15 GMT
"Tony T. Warnock" wrote:
> The Quality of Randomness is not Strained.
... by this thread?
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Secure Digital Music Initiative cracked?
Date: 28 Apr 2001 17:22:31 GMT
Douglas A. Gwyn wrote:
>Actually the paper you're thinking of was the subject of personal
>attention by an NSA employee working outside the proper scope of
>his duties, and the Agency didn't back him up.
But nonetheless there were still proposals (from the NSA)
that researchers should voluntarily submit their papers to
the NSA before publication for approval, weren't there?
------------------------------
From: [EMAIL PROTECTED] (Marc)
Crossposted-To: talk.politics.crypto
Subject: Re: Secure Digital Music Initiative cracked?
Date: 28 Apr 2001 18:55:10 GMT
>The suppressed paper is online. Read it while you can.
Right said. Xerox is trying to remove the paper from the web.
------------------------------
From: newbie <[EMAIL PROTECTED]>
Subject: Re: ancient secret writing
Date: Sat, 28 Apr 2001 17:36:49 -0300
Some letters are arabic or persian.
Maybe it could help you.
Viper wrote:
>
> Can somebody help me with this secret writing?
> I'm not sure if this belongs in the right group, but I hope to find a hint
> here.
> It's an extract from some postcards of my ancestors, and I guess it's some
> kind of secret writing or maybe a style of steno??
> The poststamp on the card dates from 1913, Ireland.
>
> See the attachment for the extract.
>
> Thanks in advance!
>
> --
> -"If it ain't broke, don't fix it."
> Greets, Viper
>
> [Image]
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: SHA PRNG
Reply-To: [EMAIL PROTECTED]
Date: Sat, 28 Apr 2001 21:52:58 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
: "Tim Tyler" <[EMAIL PROTECTED]> wrote in message
:> [...] State compromise inevitably reveals future output - but
:> need not reveal past output.
:> Hashing the internal state and feeding it back is one way to
:> prevent state compromises giving information about earlier states
:> of the PRNG.
: You mean
: output = Hi = HASH(R || H_i-1 || C)
: Where R is the initial random seed, C a binary counter and H_0 is
: HASH(R) ?
That's an example of hashed feedback yes. I don't think I'd hash R
each time - that seems largely a waste of time - just feed it in at H_0.
--
__________
|im |yler Try my latest game - it rockz - http://rockz.co.uk/
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: RC4 Source Code
Date: 28 Apr 2001 22:50:53 GMT
In <BwfG6.448$[EMAIL PROTECTED]> "Roger Schlafly"
<[EMAIL PROTECTED]> writes:
>At this point, there are enough independent implementations of RC4 (or
>ARC4 if you prefer) that I'd say the public description of RC4 is the one
>that defines RC4. If RSADS's version of RC4 is any different (which I
>think is very unlikely), then RSADS might have to change its code to
>conform to what everyone else accepts as the standard.
I agree it is unlikely, but the number of true RSADSI versions of RC4
vastly outnumber the public versions. Any browser uses RSA RC4. I'm
afraid if public ARC4 is incompatible the problem will be the public ARC4
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: Running Time of Factoring Algorithms
Date: 28 Apr 2001 22:55:13 GMT
In <3ae9ecb4$0$[EMAIL PROTECTED]> "Jeffrey Walton" <[EMAIL PROTECTED]>
writes:
]Thanks Bill.
]I don't see the exponential. Are you referring to bit operations? Forgive
]my ignorance.
The number n is exponential in the length of the number n.
n is approx 2^(length of n).
p and q are approx half the length of n and thus are also exponential in
n
p is approx (2^(1/2) )^(length of n)
This if your procedure is of order p, it is exponential in the length of
n.
(Note-- by "size of n" I meant length of n)
]"Bill Unruh" <[EMAIL PROTECTED]> wrote in message
]news:9cc4ok$6me$[EMAIL PROTECTED]...
]In <mF4G6.70450$[EMAIL PROTECTED]> "Tom St Denis"
]<[EMAIL PROTECTED]> writes:
]]> If a factoring algorithm ran with the following upper bound, how would it
]]> compare to the various methods that exist?
]]>
]]> n = p * q
]]>
]]> smallest of (p, q, p-q)
]Terribly. Those are all exponential in the size of n. The best known is
]subexponential. (of order exp(1.9 ln(n)^(1/3) ln(ln(n))^(2/3))-- Number
]Field
]Sieve)(The 1.9 is approximate).
------------------------------
Subject: Re: Censorship Threat at Information Hiding Workshop
From: [EMAIL PROTECTED] (Xcott Craver)
Date: Sun, 29 Apr 2001 00:05:20 GMT
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
>
> It's really very simple. The original creative work belongs to the
> person who creates it. He agrees to let use use it for certain purposes
> under certain conditions, which may or may not involve payment.
> If you agree to those terms, you are given access to the work.
> If you then do not follow the terms, you have broken a (possibly implied)
> contract.
However, you may have a valid legal defense for not following
those terms. So-called "fair use" is an example of such
usage. Fair use involves operations that would normally
be a violation of copyright, such as copying or distribution,
but which are defensible in court because they are reasonable.
[The DMCA cuts this off by making it a violation of a separate
law to perform that fair use copying, if you must circumvent
something that prevents the fair use copying.]
There are also situations in which the terms of an agreement
demand something that can not be demanded or granted.
Particularly asinine usage agreements can be invalid
simply by virtue of being asinine. Nobody would get away
with a book whose back cover insists on a pay-per-use
license agreement, or a UCITA-like agreement that forbids you
from writing a review of the work without permission.
Simply, the copyright holder does not have the power to
require such things.
-S
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: SHA PRNG
Date: Sun, 29 Apr 2001 00:08:40 GMT
=====BEGIN PGP SIGNED MESSAGE=====
Hash: SHA1
"Tim Tyler" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Tom St Denis <[EMAIL PROTECTED]> wrote:
> : "Tim Tyler" <[EMAIL PROTECTED]> wrote in message
>
> :> [...] State compromise inevitably reveals future output - but
> :> need not reveal past output.
>
> :> Hashing the internal state and feeding it back is one way to
> :> prevent state compromises giving information about earlier
> states :> of the PRNG.
>
> : You mean
>
> : output = Hi = HASH(R || H_i-1 || C)
>
> : Where R is the initial random seed, C a binary counter and H_0 is
> : HASH(R) ?
>
> That's an example of hashed feedback yes. I don't think I'd hash R
> each time - that seems largely a waste of time - just feed it in at
> H_0.
I would. Knowledge of H_i and C is enough to reconstruct the outputs
otherwise!
Tom
=====BEGIN PGP SIGNATURE=====
Version: PGPfreeware 7.0.3 for non-commercial use <http://www.pgp.com>
Comment: Key at: http://tomstdenis.home.dhs.org/key.asc
iQA/AwUBOutbZQULrT+pXe8cEQKkAACfVcbcHAqddojt5eJgMk3yzyZOToQAnRoB
oGexJSFUQ3Z6C0JPnr+3qOnR
=CGBj
=====END PGP SIGNATURE=====
------------------------------
** 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
******************************
