Cryptography-Digest Digest #406, Volume #13 Mon, 1 Jan 01 13:13:00 EST
Contents:
Re: Array shuffling (Tim Tyler)
Can anyone break these cryptograms? (daniel mcgrath)
Re: Are the classical techniques so inferior? (wtshaw)
Re: Can anyone break these cryptograms? (wtshaw)
Re: calculating 2048 bit public key ops with an 1024 bit engine? (Paul Rubin)
Re: AES in optimized x86 assembler? (Paul Rubin)
Re: Can anyone break these cryptograms? (John Stanford)
Re: Spambot Fodder, Dont Read was 7523 now 8191 (Steve Portly)
Re: AES in optimized x86 assembler? (graywane)
Re: Are the classical techniques so inferior? (John Savard)
Re: AES in optimized x86 assembler? (Dido Sevilla)
A simple Modular Arithmetic problem ("P.C. Teo")
Re: One Way Hash Functions (Nemo psj)
Re: A simple Modular Arithmetic problem (Mok-Kong Shen)
Genomes (Mok-Kong Shen)
Re: Generating 128bit key from user password (Francois Grieu)
Re: Are the classical techniques so inferior? (Mok-Kong Shen)
Re: One Way Hash Functions (Simon Johnson)
Re: A Censorship Resistant Digital Magazine Scheme (George Weinberg)
Re: calculating 2048 bit public key ops with an 1024 bit engine? (Francois Grieu)
----------------------------------------------------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Array shuffling
Reply-To: [EMAIL PROTECTED]
Date: Sun, 31 Dec 2000 21:27:17 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
[snip Random.nextInt() and Random.nextLong()]
: If one wants bit sequences, I suppose the better way is
: to first normalize to reals in [0,1) and then multiply to
: obtain integers of a suitable range.
If I didn't use my own homebrew stuff for this sort of thing,
I would probably use the unsynchronised version of Sean Luke's Java
Mersenne Twister - from http://www.cs.umd.edu/users/seanl/gp/
The only good reason I can see for trying to use Sun's generator is to
minimise program size, by relying on library code.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Surf against sewage.
------------------------------
From: [EMAIL PROTECTED] (daniel mcgrath)
Crossposted-To: rec.puzzles
Subject: Can anyone break these cryptograms?
Date: Sun, 31 Dec 2000 23:19:58 GMT
Below are two cipher messages encrypted using the exact same system --
keys and all. Although the two cryptograms show little resemblance to
one another, their plaintexts say very similar things, with only a
slight difference. I would be interested in seeing if any of you on
rec.puzzles or sci.crypt are able to decipher the messages, or at
least make hypotheses.
Good luck!
Advth'xance,
Daniel
Cryptogram #1:
BHNIM GKVIJ USKWG WHKGG HTGKS VIAIU LLAUT USUMU XKUUW ISXUL
GSSVW BIVJG IGJKW THXKW VUXUU OYIUB OLVDP WTASS YSJKS IGGHU
Cryptogram #2:
BIQHO KHUKG IUSIU GXXUI HGITG KSGXI ILUIZ IUUWW UWWTW TKXTU
LTUXI XGSWS SKKTB UKKHI KTSKI JVBUW NUXXX VOCIM IOLUC ZQUSK
USETW HGSHG GKXH
(WARNING: I did not use a computer to encipher these messages, so
there may be an error or two somewhere. I think they're all right,
though.)
==================================================
daniel g. mcgrath
a subscriber to _word ways: the journal of recreational linguistics_
http://www.wordways.com/
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Are the classical techniques so inferior?
Date: Sun, 31 Dec 2000 19:12:44 -0600
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
>
> Don't multiple rounds of word substitution and transposition just amount
> to a different, single round of word substitution and transposition? If
> so, where would the extra strength come from?
>
> Simon
>
Substitution and transposition can involve different information units or
multiple of units. Let's say that you substitute in a set of 32
characters, then transpose groups of 5 characters, but at the bit level,
five bits per character, 25 bits to the group. If you substituted,
transposed, and substituted again, the keyspace is equivalent to 117.7 +
83.7 + 117.7 bits. But, don't be too quickly hypnotized by the size of
the keyspace here.
--
History repeats itself when given the opportunity.
Question repeating old mistakes.
Be certain of the outcome.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Crossposted-To: rec.puzzles
Subject: Re: Can anyone break these cryptograms?
Date: Sun, 31 Dec 2000 19:18:08 -0600
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (daniel
mcgrath) wrote:
> (WARNING: I did not use a computer to encipher these messages, so
> there may be an error or two somewhere. I think they're all right,
> though.)
>
Unless you have a good record as a cipher clerk, best not to get stung,
but do a simple program to check your work. Everytime I break my own rule
here, I remeet Murphy.
The unknown-cipher challenge is for many their cup of tea, especially with
classical choices, so you may get a response; otherwise, expect
complaints.
--
History repeats itself when given the opportunity.
Question repeating old mistakes.
Be certain of the outcome.
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Crossposted-To: sci.math.num-analysis
Subject: Re: calculating 2048 bit public key ops with an 1024 bit engine?
Date: 31 Dec 2000 18:23:18 -0800
Francois Grieu <[EMAIL PROTECTED]> writes:
> I'd appreciate references. Given a black box that performs A^e mod N
> for n-bit arguments, I see simply no way at all to extend to 2n-bit.
> Given a black box that performs A*B mod N, the best method I see
> involves using the black box as a multiplier of n/2 bit arguments
> into n bit arguments, without modular reduction.
If we're talking about a typical crypto coprocessor found on something
like a smart card, in all likelihood it can do multiplication as well
as modexp. Multiplication is needed for DSA signatures and so on.
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: AES in optimized x86 assembler?
Date: 31 Dec 2000 18:24:31 -0800
[EMAIL PROTECTED] (graywane) writes:
> 1. run the C code through "gcc -O2 -S" on your platform
>
> 2. hand optimize the assembly code for your platform
>
> Good luck. GCC will produce code good enough for almost every application. I
> would question whether or not you really need hand optimized assembly. Every
> other part of your program will likely be C code anyway. Are you sure most
> of your time will actually be spend running AES code?
Depends on the application.
> Premature optimization is the root of all evil.
Yes, but now that AES is fully specified and nonoptimized reference
implementations already exists, optimizing the hell out of it is no
longer premature.
------------------------------
From: John Stanford <[EMAIL PROTECTED]>
Crossposted-To: rec.puzzles
Subject: Re: Can anyone break these cryptograms?
Date: Mon, 01 Jan 2001 02:29:07 GMT
does it use a key or is it a fixed key/no key algoritm?
daniel mcgrath wrote:
> Below are two cipher messages encrypted using the exact same system --
> keys and all. Although the two cryptograms show little resemblance to
> one another, their plaintexts say very similar things, with only a
> slight difference. I would be interested in seeing if any of you on
> rec.puzzles or sci.crypt are able to decipher the messages, or at
> least make hypotheses.
>
> Good luck!
>
> Advth'xance,
> Daniel
>
> Cryptogram #1:
>
> BHNIM GKVIJ USKWG WHKGG HTGKS VIAIU LLAUT USUMU XKUUW ISXUL
> GSSVW BIVJG IGJKW THXKW VUXUU OYIUB OLVDP WTASS YSJKS IGGHU
>
> Cryptogram #2:
>
> BIQHO KHUKG IUSIU GXXUI HGITG KSGXI ILUIZ IUUWW UWWTW TKXTU
> LTUXI XGSWS SKKTB UKKHI KTSKI JVBUW NUXXX VOCIM IOLUC ZQUSK
> USETW HGSHG GKXH
>
> (WARNING: I did not use a computer to encipher these messages, so
> there may be an error or two somewhere. I think they're all right,
> though.)
>
> --------------------------------------------------
> daniel g. mcgrath
> a subscriber to _word ways: the journal of recreational linguistics_
> http://www.wordways.com/
------------------------------
From: Steve Portly <[EMAIL PROTECTED]>
Subject: Re: Spambot Fodder, Dont Read was 7523 now 8191
Date: Sun, 31 Dec 2000 23:02:18 -0500
[EMAIL PROTECTED] wrote:
> [EMAIL PROTECTED]
> rmlwehcsjtxrhytgyccnrsdsgpuzxlziedhyxxqtfkocnejqc
------------------------------
From: [EMAIL PROTECTED] (graywane)
Subject: Re: AES in optimized x86 assembler?
Date: Mon, 01 Jan 2001 04:35:32 GMT
In article <[EMAIL PROTECTED]>, Paul Rubin wrote:
> > Premature optimization is the root of all evil.
>
> Yes, but now that AES is fully specified and nonoptimized reference
> implementations already exists, optimizing the hell out of it is no
> longer premature.
True. However, most people will "optimize the hell" out of AES and not the
rest of their application. The result will be a fast AES section that
probably is a very small percentage of the overall execution time for the
application as a whole. In the end, how much time will you really save and
how much will it have cost you in man hours? For most people it will be very
little.
Optimized assembly is also very hard for non-technical people to verify for
code correctness. You have the possibility that bugs exist longer before
they are noticed because fewer people are actually looking at the code.
There is a reason people don't write programs in assembly much anymore.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Are the classical techniques so inferior?
Date: Mon, 01 Jan 2001 06:33:36 GMT
On Sun, 31 Dec 2000 19:12:44 -0600, [EMAIL PROTECTED] (wtshaw) wrote,
in part:
>Substitution and transposition can involve different information units or
>multiple of units.
That's true, and that's the only way that one could indeed obtain a
high degree of strength through this with multiple rounds.
The original post by Mok-Kong Shen, however, didn't suggest this
possibility, but instead a different one: that the substitution would
be polyalphabetic.
Following a polyalphabetic substitution by a transposition does
conceal whatever mechanism was used to vary the polyalphabetic
substitution from one letter to the next. So that wasn't completely
useless, but I have to agree that it would not achieve reasonable
strength as directly as repeated fractionation would.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Dido Sevilla <[EMAIL PROTECTED]>
Subject: Re: AES in optimized x86 assembler?
Date: Mon, 01 Jan 2001 15:39:38 +0800
Marc wrote:
>
> Do already optimized x86 Assembler versions of AES exist as
> source code?
I wrote one for *16-bit* x86 assembler (i.e. 8086, 80186, 80286). You
can find it on the Rijndael home page. I was writing a 32-bit version,
using MMX instructions and such, but it doesn't work yet...
--
Rafael R. Sevilla <[EMAIL PROTECTED]> +63 (2) 4342217
ICSM-F Development Team, UP Diliman +63 (917) 4458925
OpenPGP Key ID: 0x0E8CE481
------------------------------
From: "P.C. Teo" <[EMAIL PROTECTED]>
Subject: A simple Modular Arithmetic problem
Date: Mon, 1 Jan 2001 16:27:28 +0800
Reply-To: "P.C. Teo" <[EMAIL PROTECTED]>
One generator g of prime order q modulo p [that is g^q = 1 (mod p)]
Random pick a number x modulo q. Is it possible for me to split the number
x?
What I mean is, I randomly pick another number x1, then I try get number x2
by having the equation hold
x = x1 + x2 (mod q)
so, is it the following equation will be true?
g^x = g^x1 * g^x2 (mod p)
since g^x1 * g^x2 = g^(x1+x2) = g^x (mod p)
Honestly, I couldn't get the last equation hold. Why?
------------------------------
From: [EMAIL PROTECTED] (Nemo psj)
Date: 01 Jan 2001 10:23:27 GMT
Subject: Re: One Way Hash Functions
yeah i was going to use MD5 in a stream cipher arrangment so what your telling
me is that this is not a good idea?
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: A simple Modular Arithmetic problem
Date: Mon, 01 Jan 2001 12:28:49 +0100
"P.C. Teo" wrote:
>
> One generator g of prime order q modulo p [that is g^q = 1 (mod p)]
>
> Random pick a number x modulo q. Is it possible for me to split the number
> x?
>
> What I mean is, I randomly pick another number x1, then I try get number x2
> by having the equation hold
> x = x1 + x2 (mod q)
>
> so, is it the following equation will be true?
> g^x = g^x1 * g^x2 (mod p)
> since g^x1 * g^x2 = g^(x1+x2) = g^x (mod p)
>
> Honestly, I couldn't get the last equation hold. Why?
Express x in terms of x1 and x2 directly (i.e. without mod q)
and then try.
Sorry for an unfriendly remark: I suppose you don't belong
to the people (there are sometimes some) who post math
problems to this group to help them do their school course
work (in that case one should instead try sci.math).
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Genomes
Date: Mon, 01 Jan 2001 12:29:00 +0100
Does anyone happen to know the statistical properties of the
genome sequences in general? Are they sufficiently 'random'?
BTW, since the code is base 4, one can use the same to readily
transcribe any given binary sequences. This could have some
steganographical benefit, I suppose. For a paragraph that is
gibberish easily gives rise to suspicion of crypto, while the
same in the alphabet AGCT is presumably difficult to
distinguish from the result of a genetic research, if
appropriately enveloped. One could perhaps also hide information
in genuine genome sequences through modifications analogous to
what is done with graphical files.
M. K. Shen
------------------------------
From: Francois Grieu <[EMAIL PROTECTED]>
Subject: Re: Generating 128bit key from user password
Date: Mon, 01 Jan 2001 12:54:36 +0100
[EMAIL PROTECTED] (Marc) wrote�:
> In a code space critical application I want to generate a
> 128bit key from a user password/passphrase. If possible, I
> want to avoid using MD5 or a similar algorithm for that
> purpose, and instead use a block cipher (which is already
> there). The main goal is to discourage on-the-fly
> dictionary attacks.
>
> At the moment I plan to repeat N times:
>
> 1. split into two halves
> 2. use left half as key, right half as input
> 3. encrypt input with key, store result as new left half
> 4. swap both halves.
>
> Is this weak, overkill or just about right?
It is indeed a good idea to make some lengthy computation with the
password before using it, as it makes dictionary attacks harder,
even if no entropy is added.
For the purpose of discouraging dictionary attacks the algorithm
described is "just about right" IMHO. It provably loose no
entropy, as it is reversible. It can use a 64 bit cipher to
produce a 128 bit result. Even if the cipher does not use
all key bits (like DES), all bits have diffused over the whole
result for N>=3. And there is no easy shortcut for the
algorithm (except for very huge N with a possible cycle finding
attack, that does not seem a practical concern).
However I see three possible improvement areas:
1) It is also advisable that an attacker can not amortize the
computational cost of a password-guessing attack by attacking the
password of several users at a time. The usual technique is to
append a public info called 'salt' (the user id, or a random value)
to the password before doing the processing.
2) Especially after 1, a problem is that the input can be longer
than 128 bits; a possible solution is to inject the additional
keying material by XORing it say after each 8 rounds.
3) What matters for the added resistance in the whole technique is
the cost for the attacker of doing the whole transformation, and one
would wish to increase the parameter N as much as tolerable by the
user. At the end of this race, the adversary should not be able to
implement the algorithm much more efficiently than the configuration
used by the user. It comes that DES is a poor building block from
this standpoint when implemented *in software* on low end processors,
because it can not be implemented efficiently on these, and but is
so efficient in relatively affordable hardware (gate arrays and
even, to a lesser degree, on processors with MMX or Altivec).
So in this particular case, it might be best to use a custom
algorithm (which is normally a no-no) designed for utmost
efficiency on the available hardware.
Francois Grieu
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Are the classical techniques so inferior?
Date: Mon, 01 Jan 2001 13:05:32 +0100
Simon Best wrote:
>
> Don't multiple rounds of word substitution and transposition just amount
> to a different, single round of word substitution and transposition? If
> so, where would the extra strength come from?
It would in general be equivalent to using a fairly large
substitution table (number of columns of the magnitude of
the size of the message in bytes) and using a single
pseudo-random number sequence that is different from the
output of the PRNG originally employed.
M. K. Shen
------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Re: One Way Hash Functions
Date: Mon, 01 Jan 2001 16:07:06 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Nemo psj) wrote:
> yeah i was going to use MD5 in a stream cipher arrangment so what
your telling
> me is that this is not a good idea?
>
Yes. The reason is that algorithms for different purposes have
different sorts of attack which can work against them.
MD5 is designed as a hashing algorithm. Now the 'group' of attacks
that can be used against a hash varies with the 'group' that can be
used against a stream-cipher. e.g. Linear cryptanalysis doesn't work on
hashes and does on stream-ciphers. Since the designers didn't have to
worry about linear cryptanalysis during construction of MD5 they
probably won't have insured resistance to linear cryptanalysis in.
This is why it a generally a bad idea to use hashes in stream-cipher
construction. Of course, there are more problems. How many iterations
of the stream-cipher will it take before the random-stream repeats
itself? It is clear that this cycle length will probably vary from key
to key making a class of weaker keys.
Simon
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com
http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED] (George Weinberg)
Crossposted-To: alt.cypherpunks
Subject: Re: A Censorship Resistant Digital Magazine Scheme
Date: Mon, 01 Jan 2001 17:30:34 GMT
On Sun, 31 Dec 2000 11:55:19 +0100, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>
>
>George Weinberg wrote:
>>
>> A Censorship Resistant Digital Magazine Scheme
>[snip]
>
>Dumb question: Isn't it possible for a government to
>monitor/control via ISPs all internet access to 'illegal'
>stuffs and thus render such efforts futile? There are
>currently projects (in democratic countries) or actual
>realizations (in not-so-democratic countries) in that
>direction, if I don't err.
It's not really a dumb question, in fact, it's
the reason I say things like "Censorship-Resistant"
rather than "Censorship Proof".
Systems like I'm discussing tend to assume that at
least the vestiges of the rule of law will still be around
i.e. innocent until proven guilty implies you can have
a bunch of what looks like random bits sitting on your hard
drive and prosecuters would have to prove that there's
something illegal encrypted there.
If this were Nazi Germany or the Soviet Union or
the Peoples Republic of China, I wouldn't even be able
to discuss the possibility of resisting giovernment
censorship without fear of arrest.
>
>Absolute effectiveness of censorship is not possible.
>On the other hand, the fear of those that disobey
>governmental orders could also be immense. I happend
>to have some experience in that during WWII while living
>in a zone occupied by enemies, with letters censored and
>short-wave reception capability removed from radio sets.
>
>M. K. Shen
>---------------------------
>http://home.t-online.de/home/mok-kong.shen
George
------------------------------
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: Mon, 01 Jan 2001 18:46:38 +0100
Bo Lin <[EMAIL PROTECTED]> wrote :
> The original question is about how to do a 2n-bit exponentiation with
> an n-bit exponentiation hardware engine. The issue was solved long
> time ago.
Jean-Jacques Quisquater gave reference to a paper by Pascal Paillier:
Low-Cost Double-Size Modular Exponentiation or How to Stretch Your
Cryptoprocessor
<http://www.gemplus.fr/smart/r_d/publications/crypto1.htm>
The paper, which was apparently written in early 1999, describes
a clever method to perform modular exponentiation mod a 2048 bit number
using 9 modular multiplication modulus 4 numbers of about 1024 bits,
and a few extra additions, in a manner that allows chained
multiplications, followed by a final Montgomery-like reduction.
A difficulty lies in the "about 1024 bits"; 2 of the 4 moduli are
actually 1025 bit. But it could still fit some hardware, and maybe
can be circumvented using different choice of moduli.
The *9 factor is much better than the "grade school" method
(split the 2048 numbers into 512 bit digits) which has a factor of
about *32.
I'd love other references.
Francois Grieu
------------------------------
** 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
******************************
