Cryptography-Digest Digest #668, Volume #12 Wed, 13 Sep 00 06:13:01 EDT
Contents:
Re: Dickman's function (D. J. Bernstein)
Re: IDEA - PGP (Johnny Bravo)
Re: nice simple function (Mok-Kong Shen)
Re: For the Gurus (Mack)
Re: Dickman's function ("Peter L. Montgomery")
Police want help cracking code to find Enigma machine ("Dave Foulger")
Re: For the Gurus (Mok-Kong Shen)
Re: For the Gurus (Mok-Kong Shen)
Re: Kryptcon (Eric Hambuch)
Re: Kryptcon (Eric Hambuch)
Re: Kryptcon (Eric Hambuch)
Re: Crypto Related Pangrams (Mark Wooding)
Re: Encrypt/Decrypt on PC-Hard-disk! (Hagen Ploog)
R: PRNG ("Cristiano")
More of the letter ("Dave Foulger")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (D. J. Bernstein)
Crossposted-To: sci.math.num-analysis
Subject: Re: Dickman's function
Date: 13 Sep 2000 07:10:27 GMT
Francois Grieu <[EMAIL PROTECTED]> wrote:
> I'm trying to find or devise simple C code to compute Dickman's
> function.
There's a rho() function in psibound: http://cr.yp.to/psibound.html
---Dan
------------------------------
From: Johnny Bravo <[EMAIL PROTECTED]>
Subject: Re: IDEA - PGP
Date: Wed, 13 Sep 2000 03:28:44 -0400
On 10 Sep 2000 17:55:21 GMT, [EMAIL PROTECTED] (Bill Unruh) wrote:
>RC4 is not the right thing to use here as it demands a separate password
>for each file encrypted, which is not of great use for you I suspect.
You can safely reuse the password if you use a seperate IV for each
message (not much of a problem).
--
Best Wishes,
Johnny Bravo
BAAWA Knight, EAC - Temporal Adjustments Division
"The most merciful thing in the world, I think, is the inability
of the human mind to correlate all its contents." - HP Lovecraft
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: nice simple function
Date: Wed, 13 Sep 2000 09:43:30 +0200
"Douglas A. Gwyn" wrote:
>
> Actually, linearity is a standard mathematical property:
> A function f is said to be linear iff for all a,x,y (for
> which the expressions are well defined): f(a*x) = a*f(x)
> and f(x+y) = f(x)+f(y). (In algebras with just one
> operator, only the second condition applies.)
I suppose that it is the opposite concept, namely non-linearity,
that is somewhat difficult to define (to be satisfactory in all
aspects). Anyway, I don't see a definition of non-linearity
in the few algebra textbooks I possess.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Mack)
Date: 13 Sep 2000 07:39:27 GMT
Subject: Re: For the Gurus
In article <[EMAIL PROTECTED]>, "root@localhost <spamthis>"
<[EMAIL PROTECTED]> writes:
>Subject: For the Gurus
>From: "root@localhost <spamthis>" <[EMAIL PROTECTED]>
>Date: Mon, 11 Sep 2000 20:13:37 -0400
>
>If I wanted to design a simple manual system that I felt was very
>difficult to crack, what historical system would you recommend I start
>with and why?
>
>What limitations would you place upon the system in a practical
>application?
>
>In your experience, what system in practical use, as a pencil and paper
>system, offers the most security for the greatest ease?
>
>Kindly bear in mind I am talking about a practical application of a
>pencil and paper system for a non-wizard. This system will be applied
>in the real world.
>
>Please don't bother with OTP's. Though I have not eliminated that
>system, key communciation is at times a difficult proposition.
>
>-m-
>
>--
> If children don't know why their grandparents did what they
>did, shall those children know what is worth preserving and what
>should change?
>
> http://www.cryptography.org/getpgp.htm
>
>
The simplest cipher that is likely to be secure is a 'book' cipher.
If the book used is in fairly limited circulation then it is much
more likely to be secure. Obviously the bible is a bad choice.
The scheme works rather simply. Each word in the message
is replaced by a set of numbers representing a word in the book.
the usual form of numbers is page-line-word
of course the order can be changed. Arbitrary addition or
subtraction or even field operations on the numbers can
make it almost impossible to crack
However if the adversary knows what book you used its strength is
limited to the operations on the numbers. The strength of the operations
performed on the word triple which we will call N determines the
strength of the cipher.
A method I like uses a table of 1000 numbers in permuted form.
Once the triples N have been produced substitute each number
by way of the table. Then add a key to the first number. Then add
each number to the number on its left. Substitute again and repeat
by adding the last number to the first number and a second key.
Repeat for as many rounds as deemed nessessary. Then
preform one last substitution.
Special words and proper names can be included by means of a
second sheet that translates the words to specific triples.
An alternate method if the number of words used is limited
is to use only a table of word translations. And then use
the numeric method described.
This method can also be reduced to the character level.
A table of letters,numbers and space is used and a substitution
table with 37 numbers and modulo 37 addition.
Practical example:
_ is a space
0 1 2 3 4 5 6 7 8 9
0 - a b c d e f g h i j
1 - k l m n o p q r s t
2 - u v w x y z 1 2 3 4
3 - 5 6 7 8 9 0 _
then the table of 36 numbers is
00 01 02 03 04 05 06 07 08 09
0 - 16 09 13 12 30 22 05 10 27 33
1 - 29 02 18 35 00 17 07 08 15 21
2 - 01 11 34 37 06 03 24 20 31 26
3 - 04 32 28 14 23 19 25
message - hello_world
key - nice
key - 13 08 02 06
first translate 07 04 11 11 14 36 30 22 14 17 11 03
substitute 01 30 02 02 00 25 04 34 00 08 02 12
round key 13
add mod 37 14 07 09 11 11 36 03 00 00 08 10 22
note that addition and modulo can be combined to avoid large numbers
substitute 00 10 33 02 02 25 12 16 16 27 29 34
round key 08
add mod 37 05 15 11 13 15 03 15 31 10 00 29 26
substitute 22 17 02 35 17 12 17 32 29 16 26 24
round key 02
add mod 37 24 04 06 04 21 33 13 08 00 16 05 29
substitute 06 30 05 30 11 14 35 27 16 07 22 26
round key 06
add mod 37 01 31 36 29 03 17 15 05 21 28 13 02
substitute 09 32 25 26 12 08 17 22 11 31 35 13
translate j7z1mirwl60n
I could have made a mistake since this was done by
hand. Three or four rounds should be enough to provide
decent security. In this case the security is provided
by the table which must have good randomness.
Note the one I used was just a quick example.
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: "Peter L. Montgomery" <[EMAIL PROTECTED]>
Crossposted-To: sci.math.num-analysis
Subject: Re: Dickman's function
Date: Wed, 13 Sep 2000 07:34:19 GMT
In article <[EMAIL PROTECTED]>
Francois Grieu <[EMAIL PROTECTED]> writes:
>I'm trying to find or devise simple C code to compute Dickman's
>function. For non-negative reals a, this function gives the proportion
>of integers N such that the highest prime factor of N is less that N^a.
>It verifies:
> /1
>F[a] = 1 for a>=1 F[a] = 1 - | F[t/(1-t)]/t dt for 0<=a<=1
> /a
>Reference: Donald E. Knuth, The Art of Computer Programming, volume 2,
>section 4.5.4, p367 (2nd ed) or p383 (3rd ed).
>Online ref: <http://mathworld.wolfram.com/DickmanFunction.html>
>Things I tried so far are very imperfect, but here they are. It is handy
>to define the auxiliary function f[b] = F[1/b] and we get
> /b
>f[b] = 1 for 0<=b<=1 f[b] = f[c] - | f[t-1]/t dt for b>=c>=1
> /c
Andrew Granville spoke twice at a recent Algorithmic Number Theory
workshop in Berkeley, CA. Go to http://www.msri.org .
Under Publications, select Lectures on Streaming Video.
Choose the Fall 2000 lectures. He suggests using
u
u f(u) = int f(t) dt (u >= 1)
u-1
[The two sides are both zero at u = 1.
Their derivatives agree when u >= 1, so they must be equal everywhere.]
--
E = m c^2. Einstein = Man of the Century. Why the squaring?
[EMAIL PROTECTED] Home: San Rafael, California
Microsoft Research and CWI
------------------------------
From: "Dave Foulger" <[EMAIL PROTECTED]>
Subject: Police want help cracking code to find Enigma machine
Date: Wed, 13 Sep 2000 09:04:52 +0100
>From The Times, London
Enigma thief's code baffles detectives
BY ANDREW NORFOLK
DETECTIVES baffled by the theft of Bletchley Park's prized Enigma coding
machine are using codebreakers to crack intricate riddles which they hope
will lead to its recovery.
The museum that housed the �100,000 Second World War cipher device has
received a mysterious letter from someone offering to return it in exchange
for �10,000.
But the letter, typed on a wartime typewriter, is written in such an unusual
style - and signed with a word that does not exist in the English
dictionary - that police are convinced that it holds the clues to the
machine's whereabouts. Now they want to open negotiations with the author.
The Enigma machine was used by German military intelligence, the Abwehr, for
ultra secret communications between the Nazi high command.
It was stolen from a glass display case at the Buckinghamshire museum during
an open day on April 1. At least four people were involved in the raid,
which police say could not have succeeded without expert inside knowledge of
both Bletchley Park and the Enigma machine. Police have taken hundreds of
finger-prints from museum visitors, questioned staff in detail and conducted
an extensive search of the building and grounds.
Detective Chief Inspector Simon Chesterman described the letter, sent last
week, as "the most significant development in the investigation".
One sentence reads: "I have been asked by the current owner the above Enigma
machine, who purchased it in good faith (in good faith being the operative
word) to say and tell you now today, the unwitting person having no ultimate
desire of depraving your august self or anyone the pleasure to see it
again." Police have refused to reveal the unusual word which appears at the
end of the letter.
The main clue to the letter's authenticity is a photographed copy of the
unique number plate, G312, which was attached to the stolen machine.
Expert codebreakers are now studying the letter, which purports to come from
a middle man representing someone who innocently bought the Enigma machine,
not realising that it had been stolen, and who now wants to return it in
exchange for compensation equal to the sum paid and immunity from
prosecution.
Mr Chesterman said yesterday that the police were willing to deal with the
author as the letter requested.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: For the Gurus
Date: Wed, 13 Sep 2000 10:20:00 +0200
wtshaw wrote:
>
> I wonder what kinds of attacks that he wants to guard against, and how
> dedicated the attacker is apt to be. This seems important. Some very
> complicated systems fail to deliver when really tested in the real world.
You are right. The original poster wants something 'very
difficult to crack'. That 'very difficult' is not well defined.
Also he wants something 'simple', which has similar problem.
(Of course, his 'historical' is also a problem. Is e.g. the
Hill cipher historical?)
On the other hand, I believe that the ancient algorithms,
if adapted with stuffs less archaic (e.g. with a PRNG
to supply the keys dynamically) and combined (multiple
encryption) and not limited to processing the characters
of the English alphabet, can be quite good when compared
with the modern block algorithms, e.g. those that employ
the Feistel method.
M. K. Shen
============================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: For the Gurus
Date: Wed, 13 Sep 2000 10:36:05 +0200
Mack wrote:
>
> The simplest cipher that is likely to be secure is a 'book' cipher.
> If the book used is in fairly limited circulation then it is much
> more likely to be secure. Obviously the bible is a bad choice.
Fortunately, with the high production rate of books in the
literature market, the choice is nowadays not very difficult.
One can of course also select a book in a foreign language.
M. K. Shen
------------------------------
From: Eric Hambuch <[EMAIL PROTECTED]>
Subject: Re: Kryptcon
Date: Wed, 13 Sep 2000 10:47:07 +0200
[EMAIL PROTECTED] wrote:
>
> While I appreciate you taking the time to look at
> my program, I do not appreciate you being a jerk
> and telling me that it is crap. My original post
> was asking for anybody who would wish to help a
> student with his research in cryptography. If
> you can't understand that, maybe you should just
> keep your thoughts to yourself.
Sorry, but the program is *REALLY* bad. I've never seen such a bad C
program: no parameters, global variables etc.
Okay, I will try a short analysis:
1. It's just a Vigenere cipher with a (maximum) 512 byte key. So if you
have enough ciphertext and know the distribution of characters in the
plaintext (i.e. English language), you can start a ciphertext-only
attack. That is described in every book about elementary cryptanalysis
(e.g. A. Sinkov: Elementary cryptanalysis, 1968!!). On a computer it
takes only a fews seconds (for that long key maybe some minutes).
2. You don't care about overflow and correct type casting: inc =
(pow(key[i],2) * 751 - key[i]);
The function pow() returns a double, that is converted to an integer
("inc") and only the first 8 bits of that integer are really used.
That's bad style!!
3. Your "encryption function" ist
inc=(k^2*751-k)
c = p + inc mod 256;
(k = key, p =plaintext, c =ciphertext).
This can be reduced to:
c = p+(k^2*751-k) mod 256
and if you know some bytes of ciphertext and plaintext, you can solve
that equation.
Is that enough for you ?
Eric
------------------------------
From: Eric Hambuch <[EMAIL PROTECTED]>
Subject: Re: Kryptcon
Date: Wed, 13 Sep 2000 10:48:04 +0200
[EMAIL PROTECTED] wrote:
>
> While I appreciate you taking the time to look at
> my program, I do not appreciate you being a jerk
> and telling me that it is crap. My original post
> was asking for anybody who would wish to help a
> student with his research in cryptography. If
> you can't understand that, maybe you should just
> keep your thoughts to yourself.
Sorry, but the program is *REALLY* bad. I've never seen such a bad C
program: no parameters, global variables etc.
Okay, I will try a short analysis:
1. It's just a Vigenere cipher with a (maximum) 512 byte key. So if you
have enough ciphertext and know the distribution of characters in the
plaintext (i.e. English language), you can start a ciphertext-only
attack. That is described in every book about elementary cryptanalysis
(e.g. A. Sinkov: Elementary cryptanalysis, 1968!!). On a computer it
takes only a fews seconds (for that long key maybe some minutes).
2. You don't care about overflow and correct type casting: inc =
(pow(key[i],2) * 751 - key[i]);
The function pow() returns a double, that is converted to an integer
("inc") and only the first 8 bits of that integer are really used.
That's bad style!!
3. Your "encryption function" ist
inc=(k^2*751-k)
c = p + inc mod 256;
(k = key, p =plaintext, c =ciphertext).
This can be reduced to:
c = p+(k^2*751-k) mod 256
and if you know some bytes of ciphertext and plaintext, you can solve
that equation.
Is that enough for you ?
Eric
------------------------------
From: Eric Hambuch <[EMAIL PROTECTED]>
Subject: Re: Kryptcon
Date: Wed, 13 Sep 2000 11:06:24 +0200
further:
4. You don't even need the full 512 bytes of your "key".
Have you ever seen the output of your "key setup" (I won't complain on
the bad programming style anymore!):
Password: "helloyou"
and your key setup key[] is:
"helloyou........." where "...." means some unprintable characters
that ALL DEPENDS ON THE FIRST 8 BYTES!! So if I had found out the first
bytes of your key, I could use your program to decrypt the whole file!
But I that's really to much work. If you sent me an encrypted document,
that contains many zero bytes (e.g. MS Word document) I could READ your
password directly from your encrypted file!
Okay, that should be enough to show that your "algorithm" is really
worthless!!
Eric
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Crypto Related Pangrams
Date: 13 Sep 2000 09:21:01 GMT
wtshaw <[EMAIL PROTECTED]> wrote:
> Wth unlimited subject I have gotten many in the 30's-40's size range,
> a few perhaps too offensive to actually post.
If you post them encrypted using ROT13 then we can verify their use of
all 26 letters without having to be offended. ;-)
-- [mdw]
------------------------------
Date: Wed, 13 Sep 2000 11:38:27 +0200
From: Hagen Ploog <[EMAIL PROTECTED]>
Subject: Re: Encrypt/Decrypt on PC-Hard-disk!
"Steven A." wrote:
> Hello
>
> Allthough this may be slightly *off topic* please help me!
>
> Im looking for software(pc) to protect my software and documents,
> that in now way should be able to hack.
>
> But i do not want to encrypt/decrypt file for file , it should be integrated
> with dos disk-drivers or something
> like that .. All sectors should be encrypted with 3des or something like
> that!
>
> Maybe, the password is entered or with a smart-card ..
>
> Is there any good stuff like this for sale ??
> I mean REAL SAFE ...
>
> Cheers
> Steven
One of my studends build exactly an "on-the-fly-disk-crypter".
This solution is hardware based due to throughput reasons (hehe, who wants to
waste pc-cycles).
It can be easily plugged in between one's diskdrive and the motherboard. That's
all.
The key comes with a smartcard. Actually we used 3DES for encryption, but the
algorithm can be changed.
Best reason for hardware: No trojaner can *EVER* spy your key
Think about this feature before using software!
Regards
Hagen
------------------------------
From: "Cristiano" <[EMAIL PROTECTED]>
Subject: R: PRNG
Date: Wed, 13 Sep 2000 11:36:17 +0200
NP wrote:
> > e=e/double(pvalue_count-1)*2.*1e6
>
> My resuls are between 500 and 600
>
> Do you have some references ?
This result *may be* very good, but if you want to compare several
generators with my method, you must collect the same numbers of p-values for
each generator.
I have got 220 p-values from a web page of two commercial hardware RNG which
pass Diehard test; with my method the square errors are: 599 and 498 (very
good!). So, if you collect 220 p-values for your generator and obtain e<600,
then *for Diehard* your generator put out a sequence that looks like truly
random.
Furthermore, if you run Diehard several time with the same generator, you'll
see big differences in the results, so it is useful to collect 50 errors of
50 Diehard tests and then to calculate the mean and the standard deviation.
This should be done for each generator to compare.
In this way the PRNG that I have tested have a mean of about 1200-1500 and
standard deviation of about 1000-1500.
Cristiano
------------------------------
From: "Dave Foulger" <[EMAIL PROTECTED]>
Subject: More of the letter
Date: Wed, 13 Sep 2000 11:02:42 +0100
I have been asked by the current owner the above Enigma machine, who
purchased it in good faith to say and tell you now today, the unwitting
person has no ultimate desire of depraving (sic) your august self or anyone
the pleasure to see it again. It is though also not his position to freely
give the possession for nothing either as the large sum is not to be lost
that has been paid (here the police have blanked out the sum) but only on
your full acceptance which are to be published nationally, with no
conditions of escape on your part or any other person or official body
involved in this matter.
[Here police have blanked out a paragraph]
A guarantee as said before in this letter that no pursuit of the unwitting
now owner shall be made, this to get had by published notice in television
and newspaper. This condition is of utmost desire to him and must be done
for any further word can be exchanged to you on this matter. It is also of
utmost importance also in this matter the person who will be as the
negotiating medium will be afforded the same freedom of entanglement in this
matter as they are not involved only on my insistence that they contact you
to make this offer and for no other reason.
If no notice is to be seen by the day of Monday as the 18th day in September
then nothing else is to be said again.
------------------------------
** 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
******************************
