Cryptography-Digest Digest #974, Volume #10 Tue, 25 Jan 00 19:13:00 EST
Contents:
How much does it cost to share knowledge? (Tom St Denis)
ECM Factoring and RSA Speed Ups (Tom St Denis)
Re: RSA survey (Jimmy Doughan)
Re: NIST, AES at RSA conference (John Savard)
ECC & RSA re: patents, copyrights (Greg)
Re: ECM Factoring and RSA Speed Ups (David A Molnar)
Re: Court cases on DVD hacking is a problem for all of us (Bill Unruh)
Re: How much does it cost to share knowledge? (Jimmy Doughan)
Re: simplistic oneway hash (Dan Day)
Re: how to break 1timepads with the same pad used N times (Alfonso De Gregorio)
OOOOH! Private Pictures... Cracked :-) (JPeschel)
code still unbroken ("Chuck Davis")
RSA v. Pohlig-Hellman (Greg)
Re: "Trusted" CA - Oxymoron? ("Douglas A. Gwyn")
Strong stream ciphers besides RC4? (Albert Yang)
Is tiger hash secure? Any java implementations? (Albert Yang)
Re: Java's RSA implimentation (Eric Lee Green)
Re: OOOOH! Private Pictures... Cracked :-) (John Savard)
Re: RSA v. Pohlig-Hellman (John Savard)
Re: LSFR ("r.e.s.")
----------------------------------------------------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: How much does it cost to share knowledge?
Date: Tue, 25 Jan 2000 20:59:16 GMT
I just got an reservation card from NIST today. 300 bucks for student
reservation? What the f'!@#% for? I will most likely just sit their
and take notes/etc...
I think they are being a bit arrogant there.
For some of you 300 bucks [US none-the-less] may seem perfectly fine,
but for a student [and a canadian at that] it's completely insane.
That's like 450 or so CDN.
So if anyone related to nist is reading I have a message for you "Get
real!"
Sorry but had to be said.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: ECM Factoring and RSA Speed Ups
Date: Tue, 25 Jan 2000 21:06:09 GMT
First off any papers floating around about ECM? I would love to read
up on it.
Second, how do you speed up RSA when more then two primes are being
used. For argument sake let's say you have 3 384-bit primes, p, q, r.
And of course n = pqr.
--
>From what I know you can make seperate exponent keys like so
'd' is the inverse mod phi(n)
d1 = d mod p-1
d2 = d mod q-1
d3 = d mod r-1
But where does it go from there? Is it just M = C^d1^d2^d3 mod n?
Wouldn't that be slower though?
Thanks in advance,
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Jimmy Doughan <[EMAIL PROTECTED]>
Subject: Re: RSA survey
Date: Tue, 25 Jan 2000 16:55:58 -0500
Many of us use crypto tokens which don't even use the CPU. US Govt agencies are
asking for 4096.
Jimbo
Steve K wrote:
> On Wed, 19 Jan 2000 18:55:00 -0000, "Michael Scott" <[EMAIL PROTECTED]>
> wrote:
>
> >In their recent paper on Cryptographic key sizes, Lenstra & Verheul
> >www.cryptosavvy.com (page 21) conclude that "Combining these observations we
> >conclude that the NFS memory requirements do not explicitly have to be taken
> >into account when extrapolating NFS run times to future processors and
> >larger RSA moduli or field sizes", where NFS is the number field sieve
> >algorithm, and the factoring method of choice for RSA moduli.
> >
> >Which I think means that they think that SPACE doesn't matter.
>
> My 2 cents: I think they meant that larger keys do not slow down the
> factoring process. OTOH, that says nothing about the staggering
> difference in sorting through possible solutions for a 512 bit key and
> a 1024 bit key.
>
> Mind you, I use big keys myself, because overkill does not cost
> extra-- at the human scale, my machine shows no different performance
> with 512 or 4096 bit keys.
>
> :o)
>
> Steve
>
> ---Continuing freedom of speech brought to you by---
> http://www.eff.org/ http://www.epic.org/
> http://www.cdt.org/
>
> PGP key 0x5D016218
> All others have been revoked.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: NIST, AES at RSA conference
Date: Tue, 25 Jan 2000 14:50:58 GMT
"Brian Gladman" <[EMAIL PROTECTED]> wrote, in part:
>Its an interesting question but even if their results are not published,
>what evidence is there that NSA will allow a knowingly weak AES solution to
>emerge when doing so will put the US information infrastructure - the most
>developed and hence the most vulnerable in the world - at risk?
>We have had 50 years when the balance of government interests have favoured
>exploitation - in my view this has now changed and the balance has shifted
>in favour of protection.
I'd like to think so, yet I don't think the government is likely to
see it that way: exploitation, after all, is useful in dealing with
something that is still a problem, international conflict; whereas for
protection against the kind of threats normally envisaged against
private industry, it is probably thought in those quarters that even
ciphers with 40-bit keys are good enough.
The thing that might change the balance of interests is not that
exploitation has become less desirable, but simply that it is
impossible to salvage.
But I'm not conversant with the success or otherwise of export
controls on microcomputer chips and related items. So, I am not sure
what obstacles might face a Third World country that decided to build
its own cipher machines from scratch (since using desktop PCs, for
example, is rather impractical - they're not rugged enough, and it's
hard to keep them from revealing secrets).
The fact that the NSA has such a large budget could be taken as an
indication that their claim that exploitation is still possible, and
export controls are worthwhile to avoid endangering it, has some
validity.
John Savard (jsavard<at>ecn<dot>ab<dot>ca)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Greg <[EMAIL PROTECTED]>
Subject: ECC & RSA re: patents, copyrights
Date: Tue, 25 Jan 2000 22:18:10 GMT
How can RSA patent even exist if it is based upon implementing
simple a mathematical operation?
And given the answer to that, is it likely something similar
will happen with ECC technology? Or is there enough prior
publications in circulation to prevent this?
I guess I am wondering if ECC has a future that looks like it
will always remain free of patent obsticals?
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: ECM Factoring and RSA Speed Ups
Date: 25 Jan 2000 22:26:25 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
> First off any papers floating around about ECM? I would love to read
> up on it.
Certicom has white papers.
> Second, how do you speed up RSA when more then two primes are being
> used. For argument sake let's say you have 3 384-bit primes, p, q, r.
> And of course n = pqr.
Chinese remaindering. Normally you would have to do 1 1152-bit
exponentiation. Now you can do 3 384-bit exponentiations.
This is actually a speedup, because exponentiation is a
O(n^3) process, while multiplication is O(n^2) .
-David
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: Court cases on DVD hacking is a problem for all of us
Date: 25 Jan 2000 22:31:23 GMT
In <[EMAIL PROTECTED]> [EMAIL PROTECTED]
(Troed) writes:
]http://slashdot.org/article.pl?sid=00/01/25/0827258
]This has the potential to stop a lot of what is being done in the
]cryptographic industry. What Jon and a few others did was to reverse
]engineer an existing crypto algorithm, find out its weaknesses, and
]then use and publish their knowledge.
]Question yourselves - how many of us professional and hobbyist
]cryptographers haven't reverse engineered crypto algorithms?
Reverse engineering is a well established right in the USA at least.
Copyright, patent and trade secret law all allow it as far as I know.
The only thing is
that the US gov't passed an attrocious law about a year ago making
breaking of crypto used to protect a copyright a crime. This law was a
total travesty of 500 years of copyright law, and is pure and simple a
law passed to enrich certain people. The Soviet Union fell, and the US
decided that they had to take over their attitudes in stuffing money
into friends pockets by the granting of state enforced monopolies.
]I have.
]Jon Johansen also did - and then found out that Hollywood used their
]influenses to get the Norwegian government to take him in for
]questioning, sieze his equipment, threatening him (and his father)
]with several years in prison.
Wasn't Norway also the country whose police acted as the Church of
Scientology toadies in shutting down an annonymous remail?
------------------------------
From: Jimmy Doughan <[EMAIL PROTECTED]>
Subject: Re: How much does it cost to share knowledge?
Date: Tue, 25 Jan 2000 17:40:04 -0500
What is a NIST reservation? I have my own reservations about NIST, but
I'll discuss them later.
Jimbo
Tom St Denis wrote:
> I just got an reservation card from NIST today. 300 bucks for student
> reservation? What the f'!@#% for? I will most likely just sit their
> and take notes/etc...
>
> I think they are being a bit arrogant there.
>
> For some of you 300 bucks [US none-the-less] may seem perfectly fine,
> but for a student [and a canadian at that] it's completely insane.
> That's like 450 or so CDN.
>
> So if anyone related to nist is reading I have a message for you "Get
> real!"
>
> Sorry but had to be said.
>
> Tom
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Dan Day)
Subject: Re: simplistic oneway hash
Date: Tue, 25 Jan 2000 22:52:38 GMT
On Mon, 24 Jan 2000 23:30:48 -0600, [EMAIL PROTECTED] (wtshaw) wrote:
>> An encryption algorithm, on the other hand, necessarily produces
>> a unique output for every unique input.
>>
>Certain encryption algorithms can produce varieties of ciphertext outputs,
>of which each will be decipherable to the same plaintext.
Okay, okay -- for clarity, make that "necessarily produces a distinct
output for every unique input". That is, there will be no collisions.
That's what I meant, but I can see where the original wording might
have been ambiguous. Read "unique output" as "unique among outputs
produced by other possible inputs", not "unique for a given input".
--
"How strangely will the Tools of a Tyrant pervert the
plain Meaning of Words!"
--Samuel Adams (1722-1803), letter to John Pitts, January 21, 1776
------------------------------
From: Alfonso De Gregorio <[EMAIL PROTECTED]>
Subject: Re: how to break 1timepads with the same pad used N times
Date: Tue, 25 Jan 2000 16:40:34 +0100
Reply-To: Alfonso De Gregorio <[EMAIL PROTECTED]>
Salvatore Sanfilippo wrote:
> Can anyone give me some pointer about breaking one time pad
> if the same pad is used more then for 1 message?
> In other words: how can I obtain Plain1 and Plain2 if I have
> Plain1 xor Plain2 (assuming Plain1 and Plain2 english text)?
Tony T. Warnock wrote:
> C1 + C2 = P1 + X + P2 + X = P1 + P2 + X + X = P1 + P2
Exactly. It simple to find P1 and P2 without knowing OTP key.
Just took C1 + C2 (R) and go through it sequentially combineing (+)
common strings of a given language (eg. english). If in one plaintext
there is one of the common strings you have combined, this will show
you a portion of the other plaintext message. Once part of the message
has became clear it's easy to extrapolate to get the rest.
Ciao
--fhex
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: OOOOH! Private Pictures... Cracked :-)
Date: 25 Jan 2000 23:23:34 GMT
To the "Password Recovery Tools" page
of my web site I've just added a cracker for an
encryption program called "Private Pictures."
This cracker is by Suby. Within the .ZIP
file you'll find the executable, a brief readme
file, and raw win32asm source.
Suby writes:
"The encryption routine used in this
program is very weak.
"It stores the password(encrypted) in
the encrypted image file and it's
very easy to recover it as I did ;)
This program allow you to recover every
password immidiately.
"Look at what the programmer says:
'Private Pictures (PPT) protect your
images with password.
Only you can view your images !'"
The program can be found at:
http://www.mediachance.com/
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: "Chuck Davis" <[EMAIL PROTECTED]>
Subject: code still unbroken
Date: Tue, 25 Jan 2000 15:24:10 -0800
No spam, no gimmicks, no nothing . . . just an honest challenge at
www.discovervancouver.com. It's a code, and whoever breaks it wins money.
It's nearly $3,000. No commercial tie-ins, honest! The prize goes up one
cent a minute.
Chuck Davis
------------------------------
From: Greg <[EMAIL PROTECTED]>
Subject: RSA v. Pohlig-Hellman
Date: Tue, 25 Jan 2000 23:31:19 GMT
I was reading through one of counterpane's web pages on the RSA
patent. And it said basically that the Pohlig-Hellman is one
good prior art to challenge the RSA patent with.
Then I thought about the quote they used from Dr Rivest:
"To gain additional protection against sophisticated
factoring algorithms, both (p-1) and (q-1) should
contain large prime factors and gcd(p-1,q-1) should
be small."
Would Pohlig-Hellman be stronger because there is only
one prime used instead of two? Did RSA use two primes
only to make it patentable and did they compromise
strength per bit in the process?
Any thoughts would be appreciated...
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Crossposted-To:
alt.privacy,alt.security.pgp,comp.security.pgp,comp.security.pgp.discuss
Subject: Re: "Trusted" CA - Oxymoron?
Date: Tue, 25 Jan 2000 23:42:11 GMT
What one really needs is an irrevocable, unforgeable token of identity;
it would constitute proof of *continuity* of identity, but of course
not absolute identity. I.e. if the authenticator says I'm Frodo, then
everything that has been authenticated as coming from Frodo has come
from the same entity, but you don't necessarily know *any*thing else
about that entity.
------------------------------
From: Albert Yang <[EMAIL PROTECTED]>
Subject: Strong stream ciphers besides RC4?
Date: Tue, 25 Jan 2000 23:46:34 GMT
I'm looking for a strong stream cipher that isn't copyrighted. I seem
to see a large choice of block ciphers, but very few stream ciphers...
Albert
------------------------------
From: Albert Yang <[EMAIL PROTECTED]>
Subject: Is tiger hash secure? Any java implementations?
Date: Tue, 25 Jan 2000 23:45:41 GMT
I think Eli and Ross do great work, and so I was wondering if tiger was
a very secure hash. Anybody have cryptoanalysis on this hash algorithm?
Also, does anybody have this in a java implementation?
------------------------------
From: Eric Lee Green <[EMAIL PROTECTED]>
Subject: Re: Java's RSA implimentation
Date: Tue, 25 Jan 2000 16:56:56 -0700
Paul Schlyter wrote:
> In article <[EMAIL PROTECTED]>,
> Eric Lee Green <[EMAIL PROTECTED]> wrote:
>
> > Paul Schlyter wrote:
> >> If there are no way to copy the array (except in a loop where each
> >> array element is copied, one by one), arrays aren't first class
> >> citizens in the language. That's the situation in C and C++.
> >
> > Interesting definition. By that definition, Python arrays don't qualify as
> > "first class" either,
> That's the definition used when talking about C. One example:
As vs. some other language?
> struct str { int a; };
>
> void foo()
> {
> int A[100], B[100], *C;
> struct str X, Y;
> ......................
Equivalent Python code:
def foo():
a=[]
b=[]
.... # set values within arrays a and b
a=b
return
the above is quite legal in Python. What happens is that the reference count
on the object referenced by 'a' is decremented (presumably 'a' still
referenced an array object, but Python allows 'a' to refer to any Python
object type, so it may not anymore), and 'a' is set to reference the same
object as 'b' instead. (If 'a' was the last reference to the former object,
the former object is garbage collected). Python (and Perl) don't really have
an equivalent of 'int a[100]', since neither requires declarations of
variables.
In short, it is unclear whether your little definition applies to languages
which do not statically type variables and which define all variables to be
referential in nature (i.e., as being a pointer to an object in the global
object store) rather than having variables denote actual static storage
spaces.
--
Eric Lee Green [EMAIL PROTECTED]
Software Engineer Visit our Web page:
Enhanced Software Technologies, Inc. http://www.estinc.com/
(602) 470-1115 voice (602) 470-1116 fax
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: OOOOH! Private Pictures... Cracked :-)
Date: Tue, 25 Jan 2000 16:58:19 GMT
[EMAIL PROTECTED] (JPeschel) wrote, in part:
>To the "Password Recovery Tools" page
>of my web site I've just added a cracker for an
>encryption program called "Private Pictures."
And the programmer who defeated it wrote:
>"The encryption routine used in this
>program is very weak.
>"It stores the password(encrypted) in
>the encrypted image file and it's
>very easy to recover it as I did ;)
>This program allow you to recover every
>password immidiately.
That's one way to fight child pornography!
John Savard (jsavard<at>ecn<dot>ab<dot>ca)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: RSA v. Pohlig-Hellman
Date: Tue, 25 Jan 2000 16:59:59 GMT
Greg <[EMAIL PROTECTED]> wrote, in part:
>Would Pohlig-Hellman be stronger because there is only
>one prime used instead of two? Did RSA use two primes
>only to make it patentable and did they compromise
>strength per bit in the process?
With only one prime, there is no public-key property. That is what RSA
is useful for. Pohlig-Hellman is a symmetric cipher, like DES.
John Savard (jsavard<at>ecn<dot>ab<dot>ca)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: "r.e.s." <[EMAIL PROTECTED]>
Subject: Re: LSFR
Date: Tue, 25 Jan 2000 16:05:00 -0800
"Mike Rosing" wrote ...
: r.e.s. wrote:
: >
: > I'm trying to follow up on your earlier suggestions involving
: > polynomials primitive on GF(2) and GF(5).
: >
: > Can you point me to any source for the primitive trinomials
: > on GF(5) up to degree ~50? (I've found these for GF(2).)
:
: I doubt there's any literature for that. I do have some software
: which could easily be modified to look for them. In its present
: invocation it's overkill, but it can find irreducible trinomials.
:
: To prove they are primitive, you'll have to factor 5^n-1 and use
: each irreducible trinomial as the modulus, and find x^r for all
: combinations of the factors. The paper mentioned earlier in the
: thread tells how to that efficiently.
:
: Send me e-mail via [EMAIL PROTECTED] and I'll be happy to send
: the code and explain what you'll have to do to get what you're
: looking for.
:
: Patience, persistence, truth,
: Dr. mike
Before further testing, let me outline what I'm wanting to do
overall, as I would welcome critique of whether it's reasonable.
--First:
The idea is to generalize the running-key generator used in the VIC
cipher, which used a 10-digit decimal "register" for pen & paper use.
Specifically, I want to find a set of register-lengths n, for each
of which there is an "optimal" running-key generator of the form
r(i) = r(i-n) + r(i-m) (mod 10), i = n, n+1, ...
with r(0),...,r(n-1) initializing the register. (Here n > m > 0,
and the register lengths of interest are 10 <= n <= 100.)
In the literature, I find these called "lagged Fibonacci generators",
which I'll abbreviate as FG(n,m,10) for my case, not to be confused
with some authors' LFG(n,m,log2(modulus)), where the modulus is an
integer power of two.
--Second:
It's necessary that m be such that the successive digit-pairs
r(i-n), r(i-m) are easy to locate -- by eye -- in the "register",
i.e. among r(i-n), r(i-n+1),..., r(i-1). (The VIC cipher used
FG(10,9,10), i.e. the two taps were simply the first two digits.)
I think there are only four practical candidates, namely
FG(n,n-1,10), FG(n,n-2,10), FG(n,1,10), and FG(n,2,10)); that is,
m = n-1, n-2, 1, 2 -- thus restricting the primitive trinomials to
x^n + x^(n-1) + 1,
x^n + x^(n-2) + 1,
x^n + x + 1,
x^n + x^2 + 1.
--Third (***Is this right??***):
For FG(n,m,10) to be in any way "optimal", it's necessary that
x^n + x^m + 1 be primitive on GF(2) and on GF(5).
Therefore, I can simply take my list of the trinomials that are
primitive on GF(2) and that also have m = n-1, n-2, 1, or 2,
and determine which of them are also primitive on GF(5).
For 10 <= n <= 100, the list is not long:
x^11 + x^2 + 1
x^11 + x^9 + 1
x^15 + x^14 + 1
x^15 + x + 1
x^21 + x^2 + 1
x^21 + x^19 + 1
x^22 + x^21 + 1
x^22 + x + 1
x^35 + x^2 + 1
x^35 + x^33 + 1
x^60 + x^59 + 1
x^60 + x + 1
x^63 + x^62 + 1
x^63 + x + 1
Maybe *none* of them are primitive on GF(5)!?
Is it out of Maple's reach to test this, I wonder?
--
r.e.s.
[EMAIL PROTECTED]
------------------------------
** 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
******************************
