Cryptography-Digest Digest #30, Volume #10 Wed, 11 Aug 99 19:13:03 EDT
Contents:
Re: simultaneous multiple exponentiation (Peter Yodarski)
Re: Power analysis of AES candidates (David Wagner)
solitaire, cryptonomicon ([EMAIL PROTECTED])
Re: My web site is up! (Greg)
Re: My web site is up! ("Robert J. Clark")
TakeFive (wtshaw)
Re: Construction of permutation matrix (wtshaw)
Re: Crypto 99 shock - the chosen conference attack! (wtshaw)
language confusion, would it work? ("JvA Networks (DK)")
Pls help me wade through the terminology (Cliff Bowman)
Re: language confusion, would it work? (John Savard)
Re: My web site is up! (John Savard)
Re: My web site is up! ([EMAIL PROTECTED])
Re: My web site is up! (John Savard)
Re: My web site is up! (John Savard)
Re: frequency of prime numbers? (Sundial Services)
Re: brute force crackers unethical? ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: Peter Yodarski <[EMAIL PROTECTED]>
Subject: Re: simultaneous multiple exponentiation
Date: Wed, 11 Aug 1999 15:24:48 -0500
Reply-To: nobody@nowhere, com
Bob Silverman wrote:
>
> In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] wrote:
> > Hello,
> > I wish to implement (in C) simultaneous multiple exponentiation with
> > Montgomery's method. The reference I've been using is
> > _Handbook_of_Applied_Cryptography_, Menezes, et. al. In Note 14.96
> (iii)
> > it states "Any of the other exponentiation algorithms discussed in
> > section 14.6.1 can be combined with Montgomery reduction ...". I would
> > appreciate elaboration as to exactly how to modify the simultaneous
> > multiple exponentiation algorithm (14.88).
>
> Montgomery's algorithm is just a way of computing a*b mod C that uses
> no division. The classical way to do this computation is to compute
> a*b then to divide by C to get a remainder. Montgomery's algorithm
> avoids the division (at the cost of some extra multiplications).
> Whether Montgomery's method actually yields a speedup depends on how
> long your machine takes to do a division relative to how long it
> takes to do a multiplication.
>
> Computing a*b mod C is a primitive operation within any modular
> exponentiation routine. But it is separate from the method used to
> do the exponentiation.
>
> 14.88 in the HAC is not about *modular* exponentiation, but rather
> about general exponentiation. i.e. compute a^7 b^9 c^10 rather
> than a^7 b^9 c^10 mod D. Translating the former to the latter
> is easy --> just replace ordinary multiplication with modular
> multiplication.
>
> --
> Bob Silverman
> "You can lead a horse's ass to knowledge, but you can't make him think"
>
> Sent via Deja.com http://www.deja.com/
> Share what you know. Learn what you don't.
Thanks for the reply.
The arguments presumably need to be converted. Is this done by Mont(x,
R^2 mod m)?
Also, what goes into the first position of the pre-computed matrix? It
normally takes 1. Does it take R mod m instead?
Thanks again.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Power analysis of AES candidates
Date: 11 Aug 1999 13:30:03 -0700
In article <[EMAIL PROTECTED]>,
Medical Electronics Lab <[EMAIL PROTECTED]> wrote:
> I disagree with the statement that it's impossible to make a
> cipher immune from side channel attacks. [...]
> To make a PK cipher immune I can do the following: [...]
Note that it is may be much easier to make a public-key cryptosystem
immune to power analysis than a symmetric-keyed cryptosystem, because
public-key cryptosystems tend to have lots of structure which you can
exploit.
In particular, blinding the input seems like a plausible defense against
many side-channel attacks, and blinding is typically only available for
public-key (not symmetric-key) cryptosystems.
------------------------------
From: [EMAIL PROTECTED]
Subject: solitaire, cryptonomicon
Date: Wed, 11 Aug 1999 21:17:43 GMT
I just read Stephenson's Cryptonomicon and wondered a few things.
Solitaire is a secure crypto algorithm computed by shuffling
a deck of cards in a certain way. It is painfully slow, so
most messages are under 50 characters long. How much more
secure is it than using the deck of cards as a one-time pad?
That would be faster and less error-prone.
Also. I wrote some code a few years back to brute force
RC4. It could break 3-bit RC4 in less than a second, 4-bit RC4 in
2 to 10 minutes, and I extrapolated 5-bit RC4 would take two weeks.
Real RC4 (8 bit) wasn't breakable that way. Solitaire resembles
RC4, and 54 cards is somewhere between 5 and 6 bits. I've been
meaning to revisit that brute force approach and see if it works
on Solitaire, but haven't done it for months, so maybe I'll never
get around to it. (It's only practical on the plain random numbers.
Adding a message on top makes things much harder.)
Also. Half the book was about codebreakers in WWII and the other
half was present day. The best schemes in the WWII half were based
on Riemann Zeta functions. I'm not sure quite what those are,
something complex-number intensive, but they definitely aren't
Solitaire. So where did Solitaire come from in that book? Was it
a secret cipher the Societas Eruditorum used or something? There
wasn't any apparent link between Solitaire and WWII in there.
- Bob Jenkins
[EMAIL PROTECTED]
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Greg <[EMAIL PROTECTED]>
Subject: Re: My web site is up!
Date: Wed, 11 Aug 1999 21:02:38 GMT
> It sucks since the person who but up the site is obviously selling
SNAKE
> OIL.
What do you mean, selling snake oil? I thought I made it clear that I
was giving my snake oil away for free! And have you per chance taken a
look at the source code that backs up my claims?
> The design sucks so bad you can't even see the company logo.
Ciphermax is not a company. And I can see the company logo just fine.
> They where not to bright and used spaces in there image titles.
What do you mean by image, title, and spaces?
> But don't worry
> if you really have such wonderful PR dirrectly from
> the NSA I am sure some
> one will be dumb enough to BUY. Just hope they
> have the same defective
> browser to view the page.
That PR is put in there for the benefit of BXA and Commerce so they
will do their home work first before they come bother me.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: "Robert J. Clark" <[EMAIL PROTECTED]>
Subject: Re: My web site is up!
Date: Wed, 11 Aug 1999 17:48:05 -0400
Greg wrote:
>
>> They where not to bright and used spaces in there image titles.
>
> What do you mean by image, title, and spaces?
Don't want to get dragged into an argument, but spaces are not valid
characters in a URL:
ftp://ftp.isi.edu/in-notes/rfc1945.txt
Sections 3.2.1 and 3.2.2
MSIE can handle them, Netscape does not.
- Rob
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: TakeFive
Date: Wed, 11 Aug 1999 15:59:56 -0600
In the blinding tradition on the cutting edge of almost trivial crypto was
BLT, a Baconian Trit cipher. Now comes TakeFive which is much the same
thing in penits, base five.
Now, historically, lots of ciphers are designed around a 5 x 5
checkerboard. Of course, I've made some additions to the list in the
past, Fudge 25 and Penuche 25. It would seem that just about everything
has been done. Well, maybe yes, and maybe no.
I can't find something just like TakeFive in the literature I have. As in
BLT, the key is a single string, this time of 25 letters. In my
borderline way, I have chosen to drop W as a letter, and insert VV where
ever it occurs. This change does not have to be reversed for text to be
highly readable.
How does TakeFive work? Consider a default key:
Alphabet(T5): abcde fghij klmno pqrst uvxyz
The idea is to code each letter in plaintext in penits, then to use the
same key to find letters to represent each of the two penits involved.
Let's say that you wanted to encrypt the word HELLO. Using 1 to 5 instead
of 0 to 4, the penits are 23 15 32 32 35. You get the penit values from
finding the major group in the key containing the letter, and finding the
position of that letter within the group.
The next step is to replace the numbers with letters. The first letter in
each major group in the key can be seen as a list of alternates for the
number one same as for the other numbers. Whereever a one is, and there
is only a single case, any of the letters afkpu could be used. Since
there are two penits involved in each letter, that means 25 two letter
replacements are available to replace any plaintext letter. I add the
qualifier that you should not use two of the same letters together, so you
only have 20 options for the substitution.
Here is what the program does with Hello, Hello, Hello:
lxkzrbxlcj, vrkehvcgrt, ghpomlmqho
With the option Encrypt in Words, all non-letters pass through. If the
other option, Encrypt in Groups is used, five letter groups appear, and
every other character, spaces included, are lost. Here is the same words
done in groups:
vcktx qmqxj lmuem gmqrz lmaec vxlre
This is not supposed to be a strong cipher, but an interesting one in
stable generic tradition with definite Baconian roots. TakeFive has a key
affect, problem....in the eyes of some surely: As in BLT where there were
3! equivalent keys for each one selected, in TakeFive, there are
5!....BLT, 6, TakeFive, 120.
I include both the completion method of making a key, and a hash method.
Can this same generic mechanism be used in larger bases? Surely it can in
base 6 square of 36, base 7 square of 49 (Humm...keyboard, plus space and
shift...maybe), and even something higher.
If anyone knows of an historic name to doing this sort of manipulation in
a 5x5 checkerboard, please let me know.
--
Sometimes you have to punt, and hope for the best.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Construction of permutation matrix
Date: Wed, 11 Aug 1999 15:59:35 -0600
In article <7oruvv$c48$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
(Patrick Juola) wrote:
>... You can build any damn thing you
> like, based on whatever bizarre constraints you have in the problem
> at hand. But if you want your analysis to make sense, you want to
> describe it in the most general terms for comparison. How often
> have you seen a speedometer measuring in "furlongs per fortnight",
> or rulers marked in "sqrt(acres)"? And do you think there's a reason
> for this?
>
I will admit to be independent minded to seek the otherwise unsought, to
fathom the forbidding waters beyond the status quo. From a scientific
standpoint, choice of units is simply arbitrary, as in truth lies where
you find it, not restricted by prejudice against the unknown for political
or other herd reasons. It is best to broaden ones horizons in spite of the
fear that what you might see could also enhase your point of view to
non-acceptance of narrow interpretations of the field.
I suppose that my taste in ciphers it extremely varied, as I enjoy seeing
what I can come up with without having to cater exclusively to one of the
small ingroups in crypto. Yep, I do find myself visiting even in those
some of the time.
Perhaps my appetite in crypto is similiar to Clinton's in women, not
necessarily interested in those according to someone else that are in good
taste, but those that taste good.
--
Sometimes you have to punt, and hope for the best.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Crypto 99 shock - the chosen conference attack!
Date: Wed, 11 Aug 1999 16:03:17 -0600
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (John Savard) wrote:
>
> Hence, this is not an attack on Crypto '99 (even if their conference also uses
> the apostrophe...)
>
Reuse of well traveled names in not something foreign to those in cryptoland.
--
Sometimes you have to punt, and hope for the best.
------------------------------
From: "JvA Networks (DK)" <[EMAIL PROTECTED]>
Subject: language confusion, would it work?
Date: Wed, 11 Aug 1999 23:14:17 +0200
Well I was kind of wondering: would you be able to make a simple encryption
that would be good enough, simply because it would too difficult for a
computer algorithm to recognize the language. Say:
I have a text in English, I replace every word with a similar looking word
in, say Danish (which like most Scandivian languages is quite similar in
grammar to English):
I start with: "Two penguins were walking in the park"
I "translate" this into something, that looks like Danish, but doesn't have
any relation to the meaning of the original: "Otte dinosauruser rullede p�
en motorvej" (It means: "Eight dinosaurs were rolling on a high-way")
Then I encrypt this text with some pretty simple scrambling and keys.
My point is: The computer will find a text that is not English, it may
recognize it as Danish, and only a human who speaks the language would know
that it was nonsense.
So, scrambling a dictonary of 60.000 words or so and then replacing English
nouns with Danish nouns and English verbs with Danish verbs and so forth
(using one of the scrambled dictionaries). The weak point is that the
reciepient needs to know, which of the scrambled dictionaries was used,
otherwise he/she will end up with a Danish/Swedish/Norweigan text that
didn't make any sense, but would look allright, if you used a statistic
approach.
You could also scramble an English dictionary first, replacing English nouns
with other English nouns etc, and then use one of the scrambled Danish
dictionaries to make the final text (which may encrypt further). The only
really weak point (as I see it) would be that the reciepient would have to
know your exact procedure and which dictionaries was used.
Why do this? Well it would need human interaction to tell the computer that
the text it had decoded (if you encrypt your text in a nonsafe algorithm
afterwards), didn't make any sense. But if it was a huge system that
intercepted e-mails, decoded them, stored them in a database and sorted them
by keywords, then this method would soon screw up the database, right?
I think this might be a good approach, since computers can break most
algorithms given the time, but right now, it cannot see what is nonsense and
what isn't as long as it follows the rules of the grammar in the languages.
regards,
Jesper
------------------------------
From: Cliff Bowman <[EMAIL PROTECTED]>
Subject: Pls help me wade through the terminology
Date: Wed, 11 Aug 1999 15:09:29 -0700
Two days of web searches, flipping through _Applied Cryptography_,
and reading this newsgroup tells me that my question will be merely
tedious to the readers of this group, but I need to make progress
on this project so I'm going to ask...
What kind of algorithm do I need if I'm required to generate a
secure "passcode" given a known "seed number"? In my application,
an authorized technician wishes to make a modification to the
internal programming of an automobile ECU. The ECU performs an
authentication proceedure wherein the technician is given a "seed
number" (based on the internal clock) and must input a corresponding
"pass code." The technician gets the pass code by calling the
manufacturer with the seed number, and the manufacturer uses a
security algorithm to generate the pass code. The ECU runs the
same security algorithm and checks for a match, thus completing
the authentication.
My problem is that I can find a lot of really cool information on
stream ciphers, eliptic curve algorithms, one-time pads, and so
forth, but they really address a different kind of problem. What
I need is something small (this is an embedded application), fast,
and integer-based. Out of desperation, I've written a little C
function that "seems to work," but I don't have any
way to evaluate its performance systematically. Any and all
help would be greatly appreciated.
--Cliff
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: language confusion, would it work?
Date: Wed, 11 Aug 1999 22:48:07 GMT
"JvA Networks (DK)" <[EMAIL PROTECTED]> wrote, in part:
>Well I was kind of wondering: would you be able to make a simple encryption
>that would be good enough, simply because it would too difficult for a
>computer algorithm to recognize the language. Say:
>I have a text in English, I replace every word with a similar looking word
>in, say Danish (which like most Scandivian languages is quite similar in
>grammar to English):
>I start with: "Two penguins were walking in the park"
>I "translate" this into something, that looks like Danish, but doesn't have
>any relation to the meaning of the original: "Otte dinosauruser rullede p�
>en motorvej" (It means: "Eight dinosaurs were rolling on a high-way")
>Then I encrypt this text with some pretty simple scrambling and keys.
Since the resulting text would still have much of the redundancy of a natural
language, so a simple encryption method could still be attacked. The computer's
model of normal text would still find an alternation of consonants and vowels,
for example. Then your code would still have to be solved; if you replace nouns
with nouns, verbs with verbs, and so on, that also makes it easier.
Now then, if you replaced words with codewords made up of random letters, like
XQH, KVE, and so on, then did some simple encryption, and then used a table to
convert groups of so many letters to Danish words so that a computer would not
necessarily recognize your text message as being enciphered,
while you still would not have something as secure as you would have if you
replaced the simple encryption by something genuinely secure,
you would at least be heading in the right direction.
John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: My web site is up!
Date: Wed, 11 Aug 1999 22:54:29 GMT
Greg <[EMAIL PROTECTED]> wrote, in part:
>If you seriously want to know what I think, e-mail me your e-mail
>address and I will tell you the real story behind that statement.
Well, I *hope* this doesn't mean you are saying that Windows 95 and NT are good
operating systems as the result of a lawsuit from Microsoft on which you cannot
comment publicly.
But actually, kidding aside, these operating systems are passable, and usable by
many people, even if they have some imperfections in security and other areas.
They offer many attractive and useful features.
John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: My web site is up!
Date: Wed, 11 Aug 1999 19:03:17 -0400
> If you seriously want to know what I think, e-mail me your e-mail
> address and I will tell you the real story behind that statement.
Well, if you are running an NT system, you obviously don't care about
security...and that is not a joke either.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: My web site is up!
Date: Wed, 11 Aug 1999 22:49:52 GMT
Greg <[EMAIL PROTECTED]> wrote, in part:
>I thought I made it clear that I
>was giving my snake oil away for free!
I'll have to admit, a glance at your site did not inspire me with great
confidence or interest - but don't mind that particular critic, as if what you
were offering was...flawed...that would only mean he had competition.
John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: My web site is up!
Date: Wed, 11 Aug 1999 22:51:32 GMT
"Robert J. Clark" <[EMAIL PROTECTED]> wrote, in part:
>Don't want to get dragged into an argument, but spaces are not valid
>characters in a URL:
>ftp://ftp.isi.edu/in-notes/rfc1945.txt
>Sections 3.2.1 and 3.2.2
>MSIE can handle them, Netscape does not.
Oh, so that, and not the proxy server, is the reason I couldn't get a site that
had a picture of an old IBM calculator from a National Geographic ad...
which I eventually saw had a bunch of slide rules in it too
after replacing the spaces with %20 in the URL so that I could get there.
John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
Date: Wed, 11 Aug 1999 16:10:34 -0700
From: Sundial Services <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: frequency of prime numbers?
Don Dodson wrote:
[...]
> Now compute P, the product of all prime numbers 2..N. P is
> divisible by every prime number. Add one to the result.
> P+1 is not divisible by any prime number, and therefore P+1
> is prime. P+1 is clearly larger than N, so N must not be
> the largest prime.
The realization that "P+1 must be prime" brings up the interesting
thought that, if you know a particular prime "P", and all of the primes
that precede it, you can add any (and therefore, each) previously known
prime to "P", then add one... would each of these therefore be prime?
Would there be any others that you could miss?
In my poor untutored mind, prime-ness is beginning to sound like a
variation of the knapsack problem.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: brute force crackers unethical?
Date: Wed, 11 Aug 1999 23:01:34 GMT
In article <7os05e$b5$[EMAIL PROTECTED]>,
"Andrew Whalan" <[EMAIL PROTECTED]> wrote:
> The thing is I didn't! It was a brute force cracker, and a poor-mans
one at
> that. It was too slow and inefficent to be a real contender at the
system
> scale.
>
That's not the point. Was real life data at stake? Take the analogy
of walking around picking brief cases. You are only trying to see how
easy it is really...
> I was after the opinions of the general public, my peers if you would.
> Ethics are primarly determined by society IMHO.
Generally you would describe your attack, or present it on fake data.
I would not start on a universities computer ..
Tom
--
PGP 6.0.2i Key
http://mypage.goplay.com/tomstdenis/key.pgp
PGP 2.6.2 Key
http://mypage.goplay.com/tomstdenis/key_rsa.pgp
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
** 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
******************************
