Cryptography-Digest Digest #983, Volume #10 Wed, 26 Jan 00 21:13:01 EST
Contents:
Re: How much does it cost to share knowledge? (Keith A Monahan)
Re: RSA v. Pohlig-Hellman (Anton Stiglic)
Re: Why did SkipJack fail? (John Savard)
Re: RSA v. Pohlig-Hellman (Anton Stiglic)
Re: New to cryptology question, rolling XOR ("Jonas")
Re: New to cryptology question, rolling XOR ("Jonas")
Re: RSA v. Pohlig-Hellman (Anton Stiglic)
Re: Java's RSA implimentation (Paul Schlyter)
Re: New to cryptology question, rolling XOR ("Jonas")
Re: Why did SkipJack fail? (Vernon Schryver)
26-Dimensional cipher - is it secure (or even possible)?
([EMAIL PROTECTED])
Re: 26-Dimensional cipher - is it secure (or even possible)? (John Savard)
Re: is signing a signature with RSA risky? (Anton Stiglic)
*** ECC Strong and Weak combined (Greg)
Re: How much does it cost to share knowledge? (Tom St Denis)
Re: Does RSA use real prime ? (H. Peter Anvin)
Re: Why did SkipJack fail? (Jerry Coffin)
Re: How much does it cost to share knowledge? ("Steve Sampson")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Keith A Monahan)
Subject: Re: How much does it cost to share knowledge?
Date: 26 Jan 2000 22:11:39 GMT
Tom,
Tom St Denis ([EMAIL PROTECTED]) wrote:
: > Yeah, 300 US bucks is about enough for a nice dinner and evening on
: the
: > town. (I'd take the night out over a conference.)
: Well you must be rolling in the dough. where I come from you don't
: spend 300 dollars on a meal.
Sorry Tom, I have to agree that $300 is just about right for a very nice
dinner and say two tickets to the theatre. Spending $200 on dinner is
not hard to do. A recent dinner I took my girlfriend to, I spent about
$20 on appetizers(2, $10 trays)
$55 on (2) entrees(double filet mignon & salmon)
$80 on a good bottle of dry, red wine(cabernet 1994 vintage)
$30 on a souffle(fruit, lemon)
or $185 BEFORE the tip. It adds up fast.
A little OT,
Keith
P.S. You know you've found a nice restaurant when AFTER you've paid the
bill, you still think the food was worth it.
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: RSA v. Pohlig-Hellman
Date: Wed, 26 Jan 2000 17:42:21 -0500
Roger Schlafly wrote:
> Greg <[EMAIL PROTECTED]> wrote in message
> news:86lbo7$612$[EMAIL PROTECTED]...
> > 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.
>
> There is some dispute about this. There was going to be a
> court case on this, but the challenger was paid to destroy
> the evidence.
>
> > 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."
>
> This advice is now considered snake oil. There was a
> reason for it at the time he wrote that, but that reason
> no longer exists. Nevertheless, the advice lives on in
It is recommended that both (p-1) and (q-1) have at least
one large prime factor, so as to guard against Pollard's
p-1 factoring algorithm. See section 3.2.3 of the Handbook
of applied cryptography.
Anton
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Why did SkipJack fail?
Date: Wed, 26 Jan 2000 15:51:06 GMT
"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote, in part:
>Jerry Coffin wrote:
>> Doing some figuring, that seems to come to around $200 million US to
>> break SkipJack at a rate of one key per year -- an amount of money
>> that quite a few large companies or most government agencies could
>> afford fairly easily.
>I doubt the financial officers would approve such an expenditure
>for so little gain! $200M/key/yr is not very productive.
No large company - unless it were planning some type of criminal
activity - would do such a thing.
But the mere fact of physical possibility, when it is so easy to just
use a longer key, is enough to disqualify a cipher from use, I would
think.
John Savard (jsavard<at>ecn<dot>ab<dot>ca)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: RSA v. Pohlig-Hellman
Date: Wed, 26 Jan 2000 17:50:41 -0500
DJohn37050 wrote:
> Pohlig-Hellman is a way to attack a group and says that at least one of the
> primes should be big. For DL systems, mod p a prime, this says p-1 should have
> a lareg prime factor as p-1 is the order of the multiplicative group.
> Don Johnson
You are confusing Pohlig-Hellman algorithm with Pohlig-Hellman
cipher. The algorithm is used to compute discrete logs, the cipher
is a symmetric key-cipher.
The cipher consist of working in a group mod q, and consists of
two private keys E, D (s.t. ED = 1 mod q - 1).
To encrypt a message m, you compute c = m^E mod q,
to decrypt you compute c^D mod q,
very simple (but of course not fast...).
It was patended about 4 months after RSA's patent.
Anton
------------------------------
From: "Jonas" <[EMAIL PROTECTED]>
Subject: Re: New to cryptology question, rolling XOR
Date: Wed, 26 Jan 2000 23:48:10 +0100
Sorry to have to bother you again, i'm not sure i understand
Let say my orginal password is 1101111
Let's pretend this my text 0100110100001111
0 XOR 0 = 0
1 XOR 0 = 1
0 XOR 1 = 1
1 XOR 1 = 0
Textout.....
1100110100001111
Swap first position to XOR outcome 1101111
Textout
1000110100001111
Swap sec position to XOR outcome 1001111
Textout
1000110100001111
Swap sec position to XOR outcome 1001111
Textout
1001110100001111
Swap sec position to XOR outcome 1001111
Textout
1001110100001111
Douglas A. Gwyn skrev i meddelandet <[EMAIL PROTECTED]>...
>Jonas wrote:
>> Would a rolling XOR be hard to break?
>
>XOR is practically irrelevant here; what you described is known as a
>ciphertext-autokey system, and indeed they aren't very hard to break.
>(For one thing, most of the key is known to the interceptor!)
>A plaintext-autokey variant is somewhat harder to break, but there
>are methods to do so.
------------------------------
From: "Jonas" <[EMAIL PROTECTED]>
Subject: Re: New to cryptology question, rolling XOR
Date: Wed, 26 Jan 2000 23:52:29 +0100
Sorry about this the letter just posted while writing.......Oooops
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: RSA v. Pohlig-Hellman
Date: Wed, 26 Jan 2000 17:58:46 -0500
You would be comparing apples and oranges, since RSA is an
asymmetric cipher and Pohlig-Hellman is a symmetric cipher.
The reason one wants to have (p-1) and (q-1) to both have at
least one large factor is to guard against Pollard's p-1 factoring
algo. If you are working in some group Z*n, where you want
Discret Log to be hard, you must choose n in a safe depending
on what DL algorithms exist....
Anton
Greg wrote:
> 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: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: Java's RSA implimentation
Date: 26 Jan 2000 22:16:26 +0100
In article <[EMAIL PROTECTED]>,
Eric Lee Green <[EMAIL PROTECTED]> wrote:
> 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?
Dunno - any suggestions of such a 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.
..but it's not equivalent to the C code above, instead it's equivalent to:
void foo()
{
int *a=malloc(100*sizeof(int));
int *b=malloc(100*sizeof(int));
.... # set values within arrays a and b
free(a), a=b;
which is quite legal in C.
> 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.
Then I see one problem with Python: how would you create an actual copy
of an array? After this code:
def foo():
a=[]
b=[]
.... # set values within arrays a and b
a=b
changing e.g. a[45] would change b[45] too, wouldn't it?
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: [EMAIL PROTECTED] [EMAIL PROTECTED] [EMAIL PROTECTED]
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: "Jonas" <[EMAIL PROTECTED]>
Subject: Re: New to cryptology question, rolling XOR
Date: Thu, 27 Jan 2000 00:04:09 +0100
New try!
Sorry to have to bother you again, i'm not sure i understand
Let say my orginal password is 11011110
Let's pretend this my text 0100110100001111
0 XOR 0 = 0
1 XOR 0 = 1
0 XOR 1 = 1
1 XOR 1 = 0
1100110100001111
Swap first position to XOR outcome 11011110
1000110100001111
Swap sec position to XOR outcome 10011110
1000110100001111
Swap 3 position to XOR outcome 10011110
1001110100001111
Swap 4 position to XOR outcome 10011110
1001110100001111
Swap 5 position to XOR outcome 10010110
1001010100001111
Swap 6 position to XOR outcome 10010110
1001010100001111
Swap 7 position to XOR outcome 10010110
1001011100001111
Swap 8 position to XOR outcome 10010111
1001011100001111
New password string 10010111 applies on bit 9 to 16 creates new password
that could be used if the text were longer?
To me it seems like you never can predict the outcome without knowing the
text or password?
Isn't it so, and why?
Douglas A. Gwyn skrev i meddelandet <[EMAIL PROTECTED]>...
>Jonas wrote:
>> Would a rolling XOR be hard to break?
>
>XOR is practically irrelevant here; what you described is known as a
>ciphertext-autokey system, and indeed they aren't very hard to break.
>(For one thing, most of the key is known to the interceptor!)
>A plaintext-autokey variant is somewhat harder to break, but there
>are methods to do so.
Douglas A. Gwyn skrev i meddelandet <[EMAIL PROTECTED]>...
>Jonas wrote:
>> Would a rolling XOR be hard to break?
>
>XOR is practically irrelevant here; what you described is known as a
>ciphertext-autokey system, and indeed they aren't very hard to break.
>(For one thing, most of the key is known to the interceptor!)
>A plaintext-autokey variant is somewhat harder to break, but there
>are methods to do so.
------------------------------
From: [EMAIL PROTECTED] (Vernon Schryver)
Subject: Re: Why did SkipJack fail?
Date: 26 Jan 2000 16:06:45 -0700
In article <[EMAIL PROTECTED]>,
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
>> Doing some figuring, that seems to come to around $200 million US to
>> break SkipJack at a rate of one key per year -- an amount of money
>> that quite a few large companies or most government agencies could
>> afford fairly easily.
>
>I doubt the financial officers would approve such an expenditure
>for so little gain! $200M/key/yr is not very productive.
Perhaps so, but how much was spent on the Glomar Explorer for no
more than the optimistic hope of recovering years-old Soviet debris
from the bottom of the Pacific? What was (and perhaps is) the cost
of the various efforts to tap the Russian undersea cables?
Vernon Schryver [EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED]
Subject: 26-Dimensional cipher - is it secure (or even possible)?
Date: Wed, 26 Jan 2000 23:05:17 GMT
Hi,
I'll start by saying I am purely an amateur, so if anything I say is
ridiculous, or even impossible, ignore me.
I have an idea for a code whereby each set of 26 letters is enciphered
differently (i.e. you encipher each 26-graph). To do this you would
need a (virtual) 26-dimensional grid of numbers. Of course, there are a
huge number of keys, because you can change not only the numbers inside
the grid, but also all of the letters along the edges.
Is this feasible? Or is it even possible?
Thanx very much,
Jack
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: 26-Dimensional cipher - is it secure (or even possible)?
Date: Wed, 26 Jan 2000 16:36:46 GMT
[EMAIL PROTECTED] wrote, in part:
>I have an idea for a code whereby each set of 26 letters is enciphered
>differently (i.e. you encipher each 26-graph).
Yes, that is perfectly possible, although only if you use a method
that doesn't involve choosing absolutely arbitrary replacements for
each 26-graph.
Binary block ciphers operate on 64-bit and 128-bit blocks, so the size
of the unit is not an obstacle. The Hill cipher, for example, can
certainly be scaled up to 26-graphs.
John Savard (jsavard<at>ecn<dot>ab<dot>ca)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: is signing a signature with RSA risky?
Date: Wed, 26 Jan 2000 18:41:38 -0500
Tim Tyler wrote:
> A compressor with an accurate model of the data will not just make it more
> difficult to detect a correct message from an incorrect one, it can make
> it *massively* more difficult.
Not true at all. If a compressor is used, the attacker will probably have his
hands on it, it won't complicate stuff much for him at all! This is what
people tend to forget...
Anton
------------------------------
From: Greg <[EMAIL PROTECTED]>
Subject: *** ECC Strong and Weak combined
Date: Thu, 27 Jan 2000 00:13:45 GMT
I was doing some testing recently with my ECC code and I noticed
that if I have a curve over a large field and a key that has the
most significant bit set, it takes about one second to complete
a point operation.
Yet, if I keep the key value very small where, say, the 80% MSBs
are clear, then the operation is very fast. This makes me think
that given a very strong public key for a server, a client can
use a random small private key which can be used to quickly generate
both the client's public key and shared secret. The client side
is very fast on these operations because its private key is
small. The client's public point is then sent to the server
and the server performs a point operation of its own to derive
the same shared secret.
While the server takes as long as usual, the benefits of this
strategy (limiting the client private key size) include:
Faster client key setup
Faster client secret setup
Weak secret does not weaken server public key
Any thoughts?
--
The only vote that you waste is the one you never wanted to make.
RICO- we were told it was a necessary surrender of our civil liberties.
Asset Forfeiture- the latest inevitable result of RICO.
http://www.ciphermax.com/book
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: How much does it cost to share knowledge?
Date: Thu, 27 Jan 2000 00:27:59 GMT
In article <[EMAIL PROTECTED]>,
Jeff Williams <[EMAIL PROTECTED]> wrote:
>
> --------------DFBDFBD128620EDD0A96C04D
> Content-Type: text/plain; charset=us-ascii
> Content-Transfer-Encoding: 7bit
>
> Tom,
>
> I had in the back of my mind that you were in high school. I wasn't
> sure and I didn't want ot insult you so I didn't mention it in my
> previous post. Basically, my point was that the student rates
> weren't really aimed at you.
I am not insulted by my age or place. I am proud of the work I have
done. The ammount of number theory I have learnt this year alone,
while albeit crude and rudimentary gives my teachers the
heebeegeebees.
I think all I need is some direction, which is one reason I wanted to
attend.
> Your idea about checking out career/school choices isn't half bad.
> Do keep in mind that the organizers of the conference have costs
> other than the hall. They have to pay the costs of the speakers
(hotel,
> airfare, food, etc). They probably have to hire folks to handle
> registrations, etc. It all adds up. $300 for a professional level
> conference ain't at all bad. Most of the conferences of interest to
> me, professionally, run into 4 figures for, typically, 3 days.
But this is a two day conference with *guest* speakers from the five
teams. They should not get paid for it. They are trying to present
their *own* work, not someone elses.
> Yeah, it's hard to cope with not being able to do what you want. But,
> heck, when I was in high school, I wanted a new car and I couldn't
> afford that. Different stages of life, and all that hoooey.
Well my ambition right now is not getting a new car, or neato hair
cut. I want to learn about math and science, and quite frankly high
school is too slow...
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (H. Peter Anvin)
Subject: Re: Does RSA use real prime ?
Date: 26 Jan 2000 17:09:52 -0800
Reply-To: [EMAIL PROTECTED] (H. Peter Anvin)
Followup to: <86kqcs$ohq$[EMAIL PROTECTED]>
By author: Greg <[EMAIL PROTECTED]>
In newsgroup: sci.crypt
>
> > First off the primality testing on PGP is such that the
> > odds of you winning the lottery jackpot within 5 seconds
> > of being struck by lightning is a much more likely
> > occurence than a PGP chosen pair of primes containing
> > a composit number.
>
> And how remote is that? Is it as remote as someone winning the
> lottery in CA twice in one decade? That has happened. :)
>
No. Someone claimed the probability is approximately 10^-44 (2^-146).
Your risk of getting killed by a meteorite while generating the key is
approximately 10^20 (100,000,000,000,000,000,000) times likelier.
-hpa
P.S. Watch out for those meteroites...
--
<[EMAIL PROTECTED]> at work, <[EMAIL PROTECTED]> in private!
"Unix gives you enough rope to shoot yourself in the foot."
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: Why did SkipJack fail?
Date: Wed, 26 Jan 2000 18:36:21 -0700
In article <86nb4p$1g4$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
[ ... ]
> At the time Deep Crack was built, the designers deliberately
> used "sub-optimal" (slightly older) chip technology, because
> they were cheaper. Sure, they ran 2x slower, but if you can
> buy 4x more of them, it's a net win. (I'm making the numbers
> up, obviously.)
> Did you remember to take this factor into account?
Sort of -- it's using technology that's in production right now. I'm
guessing that it would take long enough to design the machine that by
the time you built it, this technology would be at least one and
perhaps two generations old. It's impossible to guess for sure
(without more investigation), but it might make sense to stick to .25
micron technology instead. That cuts the number of engines per chip
about in half, (for the same size of chip) but might end up making
more sense.
Unfortunately, you've got to take a few other things into account
before you can be sure: the other big factor would be clock speed. The
design geometry has quite a bit of effect on the maximum clock speed
you can plan on using. If you cut the cost by 4, but cut the number
of engines per chip in half AND cut the clock speed in half, then
you've only broken even on the chip cost -- in that case, the smaller
geometry will almost inevitably be cheaper to build into a complete
machine since you have roughly half as many PC boards to build, half
the power supply requirements, etc.
The other thing to keep in mind is that Deep-Crack was built just
about as soon as chip-foundries started to appear, making the idea
practical. There are now a LOT more chip foundries than there were
even a couple of years ago, and more of them are now right on the
cutting edge. Chip foundries started out largely as a way for chip
companies to keep their older fabs doing something useful to make a
bit more money before they were completely obsolete. Now the
situation has more or less reversed: even quite a few relatively large
companies are only doing relatively old designs in their on fabs, and
farm out all the really cutting-edge designs to chip foundries
instead.
> > Doing some figuring, that seems to come to around $200 million US to
> > break SkipJack at a rate of one key per year -- an amount of money
> > that quite a few large companies or most government agencies could
> > afford fairly easily.
>
> Interesting. These are the kind of numbers of interest.
Just keep in mind that this was a quick extrapolation based on the
assumption that it would take roughly the same chip area to build a
SkipJack encoder that ran at about the same speed as a DES encoder.
Since I've never implemented SkipJack in hardware, nor looked at
anybody else's design for it, that's only a rough guess.
Of course, there are other factors that might easily affect the
economics as well. Just for example, a company like IBM or TI that
fabricates a lot of large chips might be able to put a relatively
small SkipJack chip on each corner of a wafer, getting something like
2 or 3 free SkipJack chips per wafer they run (since chip yields
usually run between 50 and 75%). At a production rate of 3000 wafers
per month, they could have quite a few chips fairly cheaply in not too
much time. Of course, the testing, packaging, etc., wouldn't be free,
but this could still cut the cost by a substantial amount.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: "Steve Sampson" <[EMAIL PROTECTED]>
Subject: Re: How much does it cost to share knowledge?
Date: Wed, 26 Jan 2000 19:31:41 -0600
Forget about the seminars. Get the librarian to order you a copy of the
papers. Most seminars are a defect in University professors being
required to publish or die. Most of it is unreadable by undergraduates,
and even most graduate students. After you line through all the mumbo-
jumbo, you're left with six equations that prove the Earth is in an orbit
around the Sun, or at least that's their story, and they're sticking with
it.
If I was you, and I wish I was (smile), I would take the minimum classes
at the High School, and spend at least two courses at the Community
College. It's worth more to get your post algebra math at the college
level. Make sure it's not one of those calculator based courses, as they
will bury you at the University level. I used a plain old TI-35 Scientific
up to Calc-II, and then it petered out in all the spherical stuff.
Tom St Denis wrote
>
> Well my ambition right now is not getting a new car, or neato hair
> cut. I want to learn about math and science, and quite frankly high
> school is too slow...
------------------------------
** 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
******************************
