Cryptography-Digest Digest #723, Volume #9 Tue, 15 Jun 99 11:13:03 EDT
Contents:
Re: Export restrictions question (SCOTT19U.ZIP_GUY)
Re: RSA example with small numbers (Jonathan Katz)
Re: IDEA in "aplied cryptography" BRUCE SCHNEIER (Jonathan Katz)
Re: I challenge thee :) (Fiji)
Arbitrary Huffman tree and weights distribution (was: huffman code length) (Alex
Vinokur)
Speed comparison of RSA/DES/SHA1 ("Gernot Schuh")
Re: Subset alphabet encryption ([EMAIL PROTECTED])
Re: Is there a short digest for short messages? ([EMAIL PROTECTED])
Re: encrypt using ASCII 33 to 126 only? ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Export restrictions question
Date: Tue, 15 Jun 1999 13:12:58 GMT
In article <7k4mk8$irp$[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Bill Unruh) wrote:
>In <7k1nbd$cpl$[EMAIL PROTECTED]> [EMAIL PROTECTED] writes:
>
>>Can anyone provide some clarification for the encryption export
>>restrictions. Let's say my key length is 64 bits (8 bytes). However
>>all I'm doing is performing an XOR on each 8-byte block in the file from
>>beginning to end. It is obviously not any of the fancy algorithms.
>>Does that require export approval?
>
>Under the regulations, all cryptography, even ROT 13 requires a license
>to export it. All. Some gets that license more easily, some can be given
>that license in general rather than having to get a separate license for
>each and every export, but all need it.
>Of course if the Bernstein case is upheld the regulations will be
>replaced by others just as silly and you will still need a license.
Interesting I thought the Bernstien case was such that no license
scheme would be required. Do you say this because it is the law or just
using hisrory as a a fact that the politicians never follow what the court
rules as one of constitutional rights.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
http://members.xoom.com/ecil/index.htm
NOTE EMAIL address is for SPAMERS
------------------------------
From: [EMAIL PROTECTED] (Jonathan Katz)
Subject: Re: RSA example with small numbers
Date: 15 Jun 1999 09:23:37 -0400
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Gergo
Barany) writes:
|> Delurking...
|>
|> Hi. I recently got interested in the RSA algorithm and wanted to test it
|> by puncing a few numbers in my calculator, but that is harder than I
|> thought, and I didn't find any examples of this on the WWW (and the
|> examples in Applied Cryptography are too big for my calculator).
|> Here's what I did:
|> I selected two primes, p=23 and q=37 (I could use any primes, but they
|> shouldn't be a lot bigger or smaller, I felt). Their product n=851,
|> (p-1)(q-1)=792. Then, I had the RSA Algorithm Javascript Page
|> [http://www.orst.edu/dept/honors/makmur/] generate my keys...
|>
|> I chose the number 10 as my plaintext and encrypted it:
|> C=M^e mod n=10^5 mod 851=433
|>
|> Then I took the cyphertext 433 and decrypted it:
|> M=C^d mod n=433^{317} mod 851=499
|>
|> Now, as you can see, my original plaintext is not the same as the result
|> of D(E(M)). My question is, could someone with more knowledge on this
|> subject explain to me what I did wrong or point me to a place where I
|> can find an example of RSA with numbers in about the same range?
|>
|> Gergo
|>
|> --
|> UFOs are for real: the Air Force doesn't exist.
|>
|> GU d- s:+ a--- C++>$ UL+++ P>++ L+++ E>++ W+ N++ o? K- w--- !O !M !V
|> PS+ PE+ Y+ PGP+ t* 5+ X- R>+ tv++ b+>+++ DI+ D+ G>++ e* h! !r !y+
You should be able to calculate this number on any calculator with 8-digit
accuracy...the problem you had with the exponentiation likely arose due to
rounding errors.
If you really want to calculate this by your calculator, you should try:
{{{{433^2}^2}^2}^2}...etc.
reducing the number mod 851 at each step along the way to keep the number below 8
digits (or whatever the accuracy of your calc. is).
But just calculating 433^317 and reducing that will give a completely wrong
answer due to roundoff.
--
======================
Jonathan Katz
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (Jonathan Katz)
Subject: Re: IDEA in "aplied cryptography" BRUCE SCHNEIER
Date: 15 Jun 1999 09:28:43 -0400
In article <[EMAIL PROTECTED]>, chciago <"gabriel. nock"@siemens.de> writes:
|> hey, i wanted to implement the IDEA-algorythm by the sources in bruce
|> schneiers book....
|>
|> is there a fault in this codes, or am i only too silly, to copy code
|> from a book, but : "it doesn't work"
|>
|> or where can I find sources of IDEA which are working, I only want to
|> use it for myself, not in a commercial way..
|>
Don't know about the code in Schneier's book, but two other references for IDEA
implementation are: "Network Security" by Kaufman, Perlman, Speciner
and "Handbook of Applied Cryptography" published by CRC press (I forget the
author's names at the moment).
--
======================
Jonathan Katz
[EMAIL PROTECTED]
------------------------------
From: Fiji <[EMAIL PROTECTED]>
Subject: Re: I challenge thee :)
Date: Tue, 15 Jun 1999 09:12:04 -0400
> <snip>
>
> Most 'polyalphabetic' ciphers are broken by frequency analysis if I am
> not mistaken. If this is true all you have to do is understand the
> language of the plaintext and you can guess at the key.
umm I thought that most 'monoalphabetic' ciphers are broken by frequency
analysis. I assumed that 'polyalphabetic' are usually broken using
statistical attacks but I don't know if I would call them frequency
analysis.
-Fiji
>
> Tom
>
>
> Sent via Deja.com http://www.deja.com/
> Share what you know. Learn what you don't.
>
>
------------------------------
From: Alex Vinokur <[EMAIL PROTECTED]>
Crossposted-To: comp.compression,alt.comp.compression,sci.math
Subject: Arbitrary Huffman tree and weights distribution (was: huffman code length)
Date: Tue, 15 Jun 1999 12:26:41 GMT
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> Alex Vinokur wrote:
> >
>
> > For more details about worst-case code see
> > the message titled "Huffman codes and Fibonacci numbers"
> > in comp.compression
> >
> > http://www.deja.com/getdoc.xp?AN=471802979&fmt=text
> >
>
> Recently I posed a question elsewhere concerning Huffman encoding.
> Since I don't yet have any appropriate answer, I like to take this
> opportunity to repost it here:
>
> The Huffman encoding is such that a uniform frequency distribution
> gives a balanced tree while extremely non-uniform distribution
> gives a tree very remote from being balanced. For a balanced tree
> of 4 symbols, for example, a frequency distribution of 0.20, 0.20,
> 0.21, 0.39 is possible but much more extreme distributions are not
> possible.
>
> Question: Given an arbitrary Huffman tree, how can we say something
> useful in quantitative terms concerning the possilbe frequency
> distributions that correspond to it?
>
> M. K. Shen
>
Hi,
Here is something concerning weights distribution in Huffman trees.
Thanks in advance,
Alex
=================================================================
Let W = {w1, w2, ..., w#n} be
a non-decreasing sequence of positive numbers:
w1 <= w2 <= w3 <= ... <= w#n.
The W sequence is called normalized
if w1 + w2 + ... + w#n = 1.
The W sequence of integers is called 100-normalized
if w1 + w2 + ... + w#n = 100.
Let T be a Huffman tree for the W sequence.
* Level#0
/\
/ \
* * Level#1
............
* * * * ... * Level#k
............
* * * ... * Level#n (Last)
(I think) The following conditions must take place for Huffman tree:
=============================================
A-conditions : for each level of Huffman tree
=============================================
Let a1, a2, a3, ..., a#m be nodes of Level#k
(a1 is the leftest node on this level,
a#m is the rightest node on this level).
---> A-Conditions are : a1 <= a2 <= a3 <= ... <= a#m.
=============================================
=============================================
B-conditions : for each level of Huffman tree
=============================================
Let Q be a such piece of Huffman tree :
* Level#(k-2)
/\
/ \
* * Level#(k-1)
/\ /\
/ \ / \
a b c d Level#k
---> B-Condition is : (a + b) >= d.
=============================================
=================================================================
=================================================================
================= Example 1 (BEGIN) =============================
================= Balanced Huffman binary tree ==================
================= (4 terminal nodes) ============================
=================================================================
Weights : w1, w2, w3, w4 w1 <= w2 <= w3 <= w4
s3 Level#0
/\
/ \
s1 s2 Level#1
/\ /\
/ \ / \
w1 w2 w3 w4 Level#2
Tree 1 - Balanced binary Huffman tree
s1 = w1 + w2
s2 = w3 + w4
s3 = s2 + w3 = w1 + w2 + w3 + w4
-------------------------------
(Non-trivial) A-Condition is :
Level#1 :
w1 + w2 <= w3 + w4 (s1 <= s2)
B-Conditions :
Level#2 :
w1 + w2 >= w4
-------------------------------
Example of sequences for this Huffman tree:
10, 10, 10, 19 (non-normalized sequence)
20, 20, 21, 39 (100-normalized sequence)
24, 25, 25, 26 (100-normalized sequence)
=================================================================
================= Example 1 (END) ===============================
================= Balanced Huffman binary tree ==================
================= (4 terminal nodes) ============================
=================================================================
=================================================================
================= Example 2 (BEGIN) =============================
================= Left=sided Huffman binary tree ================
================= (4 terminal nodes) ============================
=================================================================
Weights : w1, w2, w3, w4 w1 <= w2 <= w3 <= w4
s3 Level#0
/\
/ \
s2 w4 Level#1
/\
/ \
s1 w3 Level#2
/\
/ \
w1 w2 Level#3 (last)
Tree 2 - Left-sided binary Huffman tree
s1 = w1 + w2
s2 = s1 + w3 = w1 + w2 + w3
s3 = s2 + w4 = w1 + w2 + w3 + w4
-------------------------------
(Non-trivial) A-Conditions are :
Level#2 :
w1 + w2 <= w3 (s1 <= w3)
Level#1 :
w1 + w2 + w3 <= w4 (s2 <= w4)
B-Conditions : None
-------------------------------
Example of sequences for this Huffman tree:
10, 10, 21, 42 (non-normalized sequence)
12, 12, 25, 51 (100-normalized sequence)
=================================================================
================= Example 2 (END) ===============================
================= Left=sided Huffman binary tree ================
================= (4 terminal nodes) ============================
=================================================================
=================================================================
================= Example 3 (BEGIN) =============================
================= Huffman binary tree ===========================
================= (4 terminal nodes) ============================
=================================================================
Weights : w1, w2, w3, w4 w1 <= w2 <= w3 <= w4
s3 Level#0
/\
/ \
s2 w4 Level#1
/\
/ \
w3 s1 Level#2
/\
/ \
w1 w2 Level#3 (last)
Tree 3 - binary Huffman tree
s1 = w1 + w2
s2 = s1 + w3 = w1 + w2 + w3
s3 = s2 + w4 = w1 + w2 + w3 + w4
-------------------------------
(Non-trivial) A-Conditions are :
Level#2 :
w3 <= w1 + w2 (w3 <= s1)
Level#1 :
w1 + w2 + w3 <= w4 (s2 <= w4)
B-Conditions : None
-------------------------------
Example of sequences for this Huffman tree:
10, 10, 19, 40 (non-normalized sequence)
12, 13, 24, 51 (100-normalized sequence)
16, 16, 17, 51 (100-normalized sequence)
=================================================================
================= Example 3 (END) ===============================
================= Huffman binary tree ===========================
================= (4 terminal nodes) ============================
=================================================================
=================================================================
================= Example 4 (BEGIN) =============================
================= Huffman binary tree ===========================
================= (4 terminal nodes) ============================
=================================================================
Weights : w1, w2, w3, w4 w1 <= w2 <= w3 <= w4
s3 Level#0
/\
/ \
w4 s2 Level#1
/\
/ \
w3 s1 Level#2
/\
/ \
w1 w2 Level#3 (last)
Tree 4 - binary Huffman tree
s1 = w1 + w2
s2 = s1 + w3 = w1 + w2 + w3
s3 = s2 + w4 = w1 + w2 + w3 + w4
-------------------------------
(Non-trivial) A-Conditions are :
Level#2 :
w1 + w2 <= w3 (s1 <= w3)
Level#1 :
w4 <= w1 + w2 + w3 (w4 <= s2)
B-Conditions : None
-------------------------------
Example of sequences for this Huffman tree:
10, 10, 21, 40 (non-normalized sequence)
12, 13, 26, 49 (100-normalized sequence)
16, 16, 33, 35 (100-normalized sequence)
=================================================================
================= Example 4 (END) ===============================
================= Huffman binary tree ===========================
================= (4 terminal nodes) ============================
=================================================================
=================================================================
================= Example 5 (BEGIN) =============================
================= Right=sided Huffman binary tree ===============
================= (4 terminal nodes) ============================
=================================================================
Weights : w1, w2, w3, w4 w1 <= w2 <= w3 <= w4
s3 Level#0
/\
/ \
w4 s2 Level#1
/\
/ \
w3 s1 Level#2
/\
/ \
w1 w2 Level#3 (last)
Tree 5 - Right-sided binary Huffman tree
s1 = w1 + w2
s2 = s1 + w3 = w1 + w2 + w3
s3 = s2 + w4 = w1 + w2 + w3 + w4
-------------------------------
(Non-trivial) A-Conditions are :
Level#2 :
w3 <= w1 + w2 (w3 <= s1)
Level#1 :
w4 <= w1 + w2 + w3 (w4 <= s2)
B-Conditions : None
-------------------------------
Example of sequences for this Huffman tree:
10, 10, 19, 38 (non-normalized sequence)
13, 13, 25, 49 (100-normalized sequence)
16, 17, 32, 35 (100-normalized sequence)
=================================================================
================= Example 5 (END) ===============================
================= Right=sided Huffman binary tree ===============
================= (4 terminal nodes) ============================
=================================================================
=================================================================
================= Example 6 (BEGIN) =============================
================= Huffman binary tree ===========================
================= (9 terminal nodes) ============================
=================================================================
Weights : w1 <= w2 <= w3 <= w4 <= w5 <= w6 <= w7 <= w8 <= w9
s8 Level#0
/\
/ \
/ \
/ \
/ \
/ \
s6 s7 Level#1
/ \ / \
/ \ / \
w8 s4 s5 w9 Level#2
/ \ /\
s2 s3 w6 w7 Level#3
/ \ / \
w3 w4 s1 w5 Level#4
/ \
w1 w2 Level#5
Tree 6 - binary Huffman tree
s1 = w1 + w2
s2 = w3 + w4
s3 = s1 + w5 = w1 + w2 + w5
s4 = s2 + s3 = w1 + w2 + w3 + w4 + w5
s5 = w6 + w7
s6 = w8 + s4 = w1 + w2 + w3 + w4 + w5 + w8
s7 = s5 + w9 = w6 + w7 + w9
s8 = s6 + s7 = w1 + w2 + w3 + w4 + w5 + w6 + w7 + w8 + w9
-------------------------------
(Non-trivial) A-Condition is :
Level#4 :
w4 <= w1 + w2 (w4 <= s1)
w1 + w2 <= w5 (s1 <= w5)
Level#3 :
w3 + w4 <= w1 + w2 + w5 (s2 <= s3)
w1 + w2 + w5 <= w6 (s3 <= w6)
Level#2 :
w8 <= w1 + w2 + w3 + w4 + w5 (w8 <= s4)
w1 + w2 + w3 + w4 + w5 <= w6 + w7 (s4 <= s5)
w6 + w7 <= w9 (s5 <= w9)
Level#1 :
w1 + w2 + w3 + w4 + w5 + w8 <= w6 + w7 + w9 (s6 <= s7)
B-Conditions :
Level#4 :
w3 + w4 >= w5
Level#3 :
None
Level#2 :
w1 + w2 + w3 + w4 + w5 + w8 >= w9 (w8 + s4 >= w9)
Level#1 :
None
-------------------------------
Example of sequences for this Huffman tree:
10, 10, 10, 10, 19, 40, 40, 58, 81 (non-normalized sequence)
3, 3, 4, 4, 7, 14, 14, 20, 31 (100-normalized sequence)
=================================================================
================= Example 6 (END) ===============================
================= Huffman binary tree ===========================
================= (9 terminal nodes) ============================
=================================================================
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: "Gernot Schuh" <[EMAIL PROTECTED]>
Subject: Speed comparison of RSA/DES/SHA1
Date: Tue, 15 Jun 1999 14:50:40 +0100
RSA generation is about 10,00 times slower than a hash function and RSA
verifcation is about 100 times slower than one SHA operation. Those are very
fough benchmarks I found.
Does anybody know where I can find some more detailed information about the
speed of RSA, DES and SHA in comparison?
Gernot
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Subset alphabet encryption
Date: Tue, 15 Jun 1999 13:14:20 GMT
In article <[EMAIL PROTECTED]>,
Kevin Driscoll <[EMAIL PROTECTED]> wrote:
> Contrary to what Tom said, this polyalphabetic scheme can be made as
secure as
> its PRNG (with come care).
With some care... anything can be made strong. A simple substitution
cipher is not strong, it could be mediocre if the language had high
entropy. I would suggest against it though.
> Does anyone reading this newsgroup have a better idea or know of other
> implementations using polyalphabetic algorithms for subset alphabet
encryption?
>
I think my idea works. Just encode it to binary and uuecndeo for the
output. Then you can use ANY algorithm and it will work.
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Is there a short digest for short messages?
Date: Tue, 15 Jun 1999 13:16:58 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Jerry Coffin) wrote:
> Just to clarify and summarize:
>
> If you have a hash with 10^6 different possible values, you can hash
> approximately 10^3 different messages, and expect to see a collision
> between some pair out of them.
>
> If you start with a predetermined message, you need to plan on
hashing
> about (10^6)/2 different random messages before you find one that
> collides with it.
>
> 500,000 is the same as (10^6)/2.
>
That is what I meant (10^6 not 10^7). You seemed to sum it up quite
well.
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: encrypt using ASCII 33 to 126 only?
Date: Tue, 15 Jun 1999 13:10:30 GMT
In article <[EMAIL PROTECTED]>,
"Kenneth N Macpherson" <[EMAIL PROTECTED]> wrote:
The process would resemble
ascii->encode->to hex->output
output->to bin->decode->ascii
Pretty simple. You can do any char you want and not worry about
printables. You should note that output will be twice the size. So a
30 char message will mean the user will have to enter 60 chars. If you
used some form of uuencode (3/4 method) they would only have to type in
30*1.25 or 38 chars.
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.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
******************************
