Cryptography-Digest Digest #843, Volume #8 Tue, 5 Jan 99 09:13:06 EST
Contents:
Re: Teaching Program (Jochen Ruetschlin)
Re: Help: a logical difficulty (Mok-Kong Shen)
Re: FAQ ??????????? ("M. DeBacle")
Re: Help: a logical difficulty (Mok-Kong Shen)
Re: Help: a logical difficulty (John Briggs)
Re: CTS a la Schneier, Rivest ([EMAIL PROTECTED])
Re: I want DSA program for free ("M. DeBacle")
Cryptography FAQ (01/10: Overview) ([EMAIL PROTECTED])
Cryptography FAQ (02/10: Net Etiquette) ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: Jochen Ruetschlin <[EMAIL PROTECTED]>
Subject: Re: Teaching Program
Date: Tue, 05 Jan 1999 12:28:33 +0100
bill_wells wrote:
>
> Does anyone know of an encryption teaching program--that is, something
> that teaches about encryption through examples or games. My friend
> thought it would be stimulating for her history classes to think
> about the World Wars in terms of codes--maybe have a decoding contest
> where the message says something like "We're going to invade on June 6"
> or the like that and give the kids 24 hours to decipher. Does anyone
> know of any programs like that?
I don't know any programs but if you're interested in cryptographic
history (esp. the World Wars) the book of David Kahn ("The Codebreakers")
is a nice and exciting lecture with many, many examples.
--
Jochen Ruetschlin
[EMAIL PROTECTED]
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Help: a logical difficulty
Date: Tue, 05 Jan 1999 13:24:06 +0100
Jonah Thomas wrote:
>
> It's possible to do this if you accept certain arbitrary ideas.
>
> For example, you could define a turing machine in a particular way,
> and then for any particular finite sequence you could find the
> minimum program for that machine that would produce that sequence.
> Since you can find a program that produces the sequence, by
> exhaustive search you could look at all the shorter programs to
> find the shortest one that produces the sequence in question. You
> could then call the length of that program the measure of
> complexity of that sequence.
Can you substantiate your phrase 'find the minimum program for that
machine'? Is there an algorithmic (terminating) method of finding
that program for a given Turing machine and a given sequence? How
about an infinite sequence?
>
> But a different machine will give different results.
This is also an essential problem. If for two given sequences
one machine says the first is less complex than the other but
the second machine says the contrary, which result should one take?
M. K. Shen
------------------------------
From: "M. DeBacle" <[EMAIL PROTECTED]>
Subject: Re: FAQ ???????????
Date: Tue, 05 Jan 1999 04:28:36 -1000
konstantinidis wrote:
>
> Can someone tell me where i will find a FAQ about crypto ?
> Please answer
http://www.cis.ohio-state.edu/hypertext/faq/usenet/cryptography-faq/
http://www.cs.auckland.ac.nz/~pgut001/links.html
http://www.dice.ucl.ac.be/crypto/biblio_ell.html
God bless your curious attitude.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Help: a logical difficulty
Date: Tue, 05 Jan 1999 13:42:01 +0100
KRamsay wrote:
>
> Some of the arguments are nonconstructive, but that isn't the same as
> their being "not well-defined". In mainstream mathematics, common use
> is made of the law of excluded middle, which has the effect of saying
> that for any proposition P, the integer n defined by n=1 if P is true
> and n=0 if P is false, exists. This is assumed, regardless of whether
> we have a way of determining whether P is true. It's built into logic
> ("classical" logic).
>
> This sort of feature isn't particular to the theory of algorithms;
> it's pervasive in mathematics. When we say that a real number always
> has a decimal expansion, it's in this nonconstructive sense of
> existence; decimals can't always be computed. To understand
> nonconstructive mathematics, you just have to get used to existence,
> in this case of the complexity of a string, not meaning that one can
> find the complexity or anything like that.
>
> Nonconstructive arguments generally can be reinterpreted in a
> constructive way, however. For example, one theorem says that there is
> a uniform upper bound on the number of minimum-length programs which
> generate any given string. That there is such a thing as "the number
> of shortest programs..." is nonconstructive, but it's only a sort of
> superficial nonconstructivity; the proof shows, constructively, that
> if we have more than a certain number of programs of the same length
> which generate the same string, we can use them to get a shorter
> program which generates the same string.
I am not (yet) quite sure that the 'implication' of non-constructiveness
in the present context is comparable to that of elsewhere in
mathematics. If a theorem says that there exists a unique solution to
a differential equation or that a certain number theoretical
equation has a solution below a certain (often very huge) bounds,
it can be satisfying, at least to some extent. But here we are
usually (at least in practical cryptology, if I don't err) interested
in the issue of comparative complexity, i.e. whether a sequence is
more complex and hence cryptologically superior than the other. The
mere existence of a length (unknown) of the shortest description
doesn't help. Nor, I guess, would even bounds be useful, since two
numbers within the same bounds may have any relative order. As
has been pointed out in another follow-up, a further complication
is that different machines could produce different (incompatible)
results.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (John Briggs)
Subject: Re: Help: a logical difficulty
Date: 5 Jan 1999 13:04:42 GMT
Reply-To: [EMAIL PROTECTED]
In article <76ri3m$[EMAIL PROTECTED]>, Jonah Thomas
<[EMAIL PROTECTED]> writes:
>Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
[snip flawed argument that confuses "uncomputable" with "undefined".]
>>What is the flaw in the above. Would experts please help? Thanks.
>
>It's possible to do this if you accept certain arbitrary ideas.
>
>For example, you could define a turing machine in a particular way,
>and then for any particular finite sequence you could find the
>minimum program for that machine that would produce that sequence.
>Since you can find a program that produces the sequence, by
>exhaustive search you could look at all the shorter programs to
>find the shortest one that produces the sequence in question. You
>could then call the length of that program the measure of
>complexity of that sequence.
You forgot the halting problem. You can't always tell the
difference between a Turing machine that will produce the string
that you're after and halt and a Turing machine that will loop
forever.
The approach you suggest is seductive, but wrong.
John Briggs [EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: CTS a la Schneier, Rivest
Date: Tue, 05 Jan 1999 13:10:27 GMT
In article <76rjjq$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Frank Gifford) wrote:
snip ...
>
> If you want to encrypt a message which has a smaller blocksize than your
> cipher, you can tack on 0 bits to the beginning, encrypt that, chop off
> the first several bits and send the answer. Your recipient then can try
> decrypting all possible starting bit values and which have the sent message
> as the remainder. When he gets a decryption starting with all zero bits,
> he knows he has the right answer. [This example is a little far fetched,
> I know - it's just for illustration.]
Actuall the above does not work since getting all zeros does not
even necessiarly mean you have the right soultion and more than one
solution can exist. I guess it means you have not played much with
encryption. There are several modes of encryption that allow short
blocks and most are enferior. Even the mode in PGP 2.6.3 is worse than
ECB since it uses a stream generated by the key only then XOR s the
result with the file to be encrypted. This allows short blocks and
any lenght files. Many codes use this method. But it sucks.
David Scott
P.S. like at common chainning modes in the FAQ
--
http://cryptography.org/cgi-bin/crypto.cgi/Misc/scott19u.zip
http://members.xoom.com/ecil/index.htm
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: "M. DeBacle" <[EMAIL PROTECTED]>
Subject: Re: I want DSA program for free
Date: Tue, 05 Jan 1999 05:26:11 -1000
M. DeBacle wrote:
>
> I want to get a free copy of the Digital Signature Algorithm (DSA). I
> prefer the source code, but executable is tolerable. I have an IBM
> compatible PC.
>
> If you know of a website where I can download it, please post the LINK
> here.
>
> I want to sign some stuff. I want to look at the source code. I might not
> modify the source code and re-compile it. I might not try to use it to
> produce an encryption/decryption program which looks like signature
> software. I might not distribute it. I absolutely will not sell it.
>
> I read in a book (Crypto '92, page 80) that "certain countries permit the
> use of signature algorithms within their borders, but they restrict the
> use of encryption algorithms". I will not send any modified DSA software
> outside of the USA. Really. I promise. I will publish the results of this
> work on sci.crypt .
I found an answer to my own questions:
ftp://ftp.compapp.dcu.ie/pub/crypto/
download the file miracl.zip and read the README file there. Also Michael
Scott's website is:
http://indigo.ie/~mscott
I will use the DSA sourcecode for research purposes and post the results
here on sci.crypt, hopefully a demonstration of a modified source code
DSA program with a menu that gives users the choice of using DSA to
encrypt and decrypt programs two ways:
1 DSA will make a one time pad for archiving files locally. Of course
there are other ways to make OTPs, but DSA will someday be widespread for
non-expert use. The modification I will make will disable the random "k"
in the the calculations so it is a fixed sub-key.
2 DSA will produce "chosen signatures" with binary values equal to coded
messages of about 8 bits per signature. A secret protocol agreement
beforehand will let two people interpret the codes in ways that outsiders
do not recognize.
NIST asked for comments to be reviewed every 5 years, so here we go...
2002 is the next review from what I can determine.
Thank you Michael Scott
M. DeBacle
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: talk.politics.crypto,sci.answers,news.answers,talk.answers
Subject: Cryptography FAQ (01/10: Overview)
Date: 5 Jan 1999 13:38:26 GMT
Reply-To: [EMAIL PROTECTED]
Archive-name: cryptography-faq/part01
Version: 1.0
Last-modified: 94/01/11
This is the first of ten parts of the sci.crypt FAQ. The parts are
mostly independent, but you should read this part before the rest. We
don't have the time to send out missing parts by mail, so don't ask.
Notes such as ``[KAH67]'' refer to the reference list in the last part.
Disclaimer: This document is the product of the Crypt Cabal, a secret
society which serves the National Secu---uh, no. Seriously, we're the
good guys, and we've done what we can to ensure the completeness and
accuracy of this document, but in a field of military and commercial
importance like cryptography you have to expect that some people and
organizations consider their interests more important than open
scientific discussion. Trust only what you can verify firsthand.
And don't sue us.
Many people have contributed to this FAQ. In alphabetical order:
Eric Bach, Steve Bellovin, Dan Bernstein, Nelson Bolyard, Carl Ellison,
Jim Gillogly, Mike Gleason, Doug Gwyn, Luke O'Connor, Tony Patti,
William Setzer. We apologize for any omissions.
If you have suggestions, comments, or criticism, please let the current
editors know by sending e-mail to [EMAIL PROTECTED] Bear in
mind that this is a work in progress; there are some questions which we
should add but haven't gotten around to yet. In making comments on
additions it is most helpful if you are as specific as possible and
ideally even provide the actual exact text.
Archives: sci.crypt has been archived since October 1991 on
ripem.msu.edu, though these archives are available only to U.S. and
Canadian users. Another site is rpub.cl.msu.edu in /pub/crypt/sci.crypt/
from Jan 1992. Please contact [EMAIL PROTECTED] if you know of
other archives.
The sections of this FAQ are available via anonymous FTP to rtfm.mit.edu
as /pub/usenet/news.answers/cryptography-faq/part[xx]. The Cryptography
FAQ is posted to the newsgroups sci.crypt, talk.politics.crypto,
sci.answers, and news.answers every 21 days.
The fields `Last-modified' and `Version' at the top of each part track
revisions.
Table of Contents
=================
1. Overview
2. Net Etiquette
2.1. What groups are around? What's a FAQ? Who am I? Why am I here?
2.2. Do political discussions belong in sci.crypt?
2.3. How do I present a new encryption scheme in sci.crypt?
3. Basic Cryptology
3.1. What is cryptology? Cryptography? Plaintext? Ciphertext? Encryption? Key?
3.2. What references can I start with to learn cryptology?
3.3. How does one go about cryptanalysis?
3.4. What is a brute-force search and what is its cryptographic relevance?
3.5. What are some properties satisfied by every strong cryptosystem?
3.6. If a cryptosystem is theoretically unbreakable, then is it
guaranteed analysis-proof in practice?
3.7. Why are many people still using cryptosystems that are
relatively easy to break?
3.8. What are the basic types of cryptanalytic `attacks'?
4. Mathematical Cryptology
4.1. In mathematical terms, what is a private-key cryptosystem?
4.2. What is an attack?
4.3. What's the advantage of formulating all this mathematically?
4.4. Why is the one-time pad secure?
4.5. What's a ciphertext-only attack?
4.6. What's a known-plaintext attack?
4.7. What's a chosen-plaintext attack?
4.8. In mathematical terms, what can you say about brute-force attacks?
4.9. What's a key-guessing attack? What's entropy?
5. Product Ciphers
5.1. What is a product cipher?
5.2. What makes a product cipher secure?
5.3. What are some group-theoretic properties of product ciphers?
5.4. What can be proven about the security of a product cipher?
5.5. How are block ciphers used to encrypt data longer than the block size?
5.6. Can symmetric block ciphers be used for message authentication?
5.7. What exactly is DES?
5.8. What is triple DES?
5.9. What is differential cryptanalysis?
5.10. How was NSA involved in the design of DES?
5.11. Is DES available in software?
5.12. Is DES available in hardware?
5.13. Can DES be used to protect classified information?
5.14. What are ECB, CBC, CFB, and OFB encryption?
6. Public-Key Cryptography
6.1. What is public-key cryptography?
6.2. How does public-key cryptography solve cryptography's Catch-22?
6.3. What is the role of the `trapdoor function' in public key schemes?
6.4. What is the role of the `session key' in public key schemes?
6.5. What's RSA?
6.6. Is RSA secure?
6.7. What's the difference between the RSA and Diffie-Hellman schemes?
6.8. What is `authentication' and the `key distribution problem'?
6.9. How fast can people factor numbers?
6.10. What about other public-key cryptosystems?
6.11. What is the `RSA Factoring Challenge?'
7. Digital Signatures
7.1. What is a one-way hash function?
7.2. What is the difference between public, private, secret, shared, etc.?
7.3. What are MD4 and MD5?
7.4. What is Snefru?
8. Technical Miscellany
8.1. How do I recover from lost passwords in WordPerfect?
8.2. How do I break a Vigenere (repeated-key) cipher?
8.3. How do I send encrypted mail under UNIX? [PGP, RIPEM, PEM, ...]
8.4. Is the UNIX crypt command secure?
8.5. How do I use compression with encryption?
8.6. Is there an unbreakable cipher?
8.7. What does ``random'' mean in cryptography?
8.8. What is the unicity point (a.k.a. unicity distance)?
8.9. What is key management and why is it important?
8.10. Can I use pseudo-random or chaotic numbers as a key stream?
8.11. What is the correct frequency list for English letters?
8.12. What is the Enigma?
8.13. How do I shuffle cards?
8.14. Can I foil S/W pirates by encrypting my CD-ROM?
8.15. Can you do automatic cryptanalysis of simple ciphers?
8.16. What is the coding system used by VCR+?
9. Other Miscellany
9.1. What is the National Security Agency (NSA)?
9.2. What are the US export regulations?
9.3. What is TEMPEST?
9.4. What are the Beale Ciphers, and are they a hoax?
9.5. What is the American Cryptogram Association, and how do I get in touch?
9.6. Is RSA patented?
9.7. What about the Voynich manuscript?
10. References
10.1. Books on history and classical methods
10.2. Books on modern methods
10.3. Survey articles
10.4. Reference articles
10.5. Journals, conference proceedings
10.6. Other
10.7. How may one obtain copies of FIPS and ANSI standards cited herein?
10.8. Electronic sources
10.9. RFCs (available from [FTPRF])
10.10. Related newsgroups
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: talk.politics.crypto,sci.answers,news.answers,talk.answers
Subject: Cryptography FAQ (02/10: Net Etiquette)
Date: 5 Jan 1999 13:38:33 GMT
Reply-To: [EMAIL PROTECTED]
Archive-name: cryptography-faq/part02
Last-modified: 94/06/13
This is the second of ten parts of the sci.crypt FAQ. The parts are
mostly independent, but you should read the first part before the rest.
We don't have the time to send out missing parts by mail, so don't ask.
Notes such as ``[KAH67]'' refer to the reference list in the last part.
The sections of this FAQ are available via anonymous FTP to rtfm.mit.edu
as /pub/usenet/news.answers/cryptography-faq/part[xx]. The Cryptography
FAQ is posted to the newsgroups sci.crypt, talk.politics.crypto,
sci.answers, and news.answers every 21 days.
Contents:
2.1. What groups are around? What's a FAQ? Who am I? Why am I here?
2.2. Do political discussions belong in sci.crypt?
2.3. How do I present a new encryption scheme in sci.crypt?
2.1. What groups are around? What's a FAQ? Who am I? Why am I here?
Read news.announce.newusers and news.answers for a few weeks. Always
make sure to read a newsgroup for some time before you post to it.
You'll be amazed how often the same question can be asked in the same
newsgroup. After a month you'll have a much better sense of what the
readers want to see.
2.2. Do political discussions belong in sci.crypt?
No. In fact some newsgroups (notably misc.legal.computing) were
created exactly so that political questions like ``Should RSA be
patented?'' don't get in the way of technical discussions. Many
sci.crypt readers also read misc.legal.computing, comp.org.eff.talk,
comp.patents, sci.math, comp.compression, talk.politics.crypto,
et al.; for the benefit of people who don't care about those other
topics, try to put your postings in the right group.
Questions about microfilm and smuggling and other non-cryptographic
``spy stuff'' don't belong in sci.crypt either.
2.3. How do I present a new encryption scheme in sci.crypt?
``I just came up with this neat method of encryption. Here's some
ciphertext: FHDSIJOYW^&%$*#@OGBUJHKFSYUIRE. Is it strong?'' Without a
doubt questions like this are the most annoying traffic on sci.crypt.
If you have come up with an encryption scheme, providing some
ciphertext from it is not adequate. Nobody has ever been impressed by
random gibberish. Any new algorithm should be secure even if the
opponent knows the full algorithm (including how any message key is
distributed) and only the private key is kept secret. There are some
systematic and unsystematic ways to take reasonably long ciphertexts
and decrypt them even without prior knowledge of the algorithm, but
this is a time-consuming and possibly fruitless exercise which most
sci.crypt readers won't bother with.
So what do you do if you have a new encryption scheme? First of all,
find out if it's really new. Look through this FAQ for references and
related methods. Familiarize yourself with the literature and the
introductory textbooks.
When you can appreciate how your cryptosystem fits into the world at
large, try to break it yourself! You shouldn't waste the time of tens
of thousands of readers asking a question which you could have easily
answered on your own.
If you really think your system is secure, and you want to get some
reassurance from experts, you might try posting full details of your
system, including working code and a solid theoretical explanation, to
sci.crypt. (Keep in mind that the export of cryptography is regulated
in some areas.)
If you're lucky an expert might take some interest in what you posted.
You can encourage this by offering cash rewards---for instance, noted
cryptographer Ralph Merkle is offering $1000 to anyone who can break
Snefru-4---but there are no guarantees. If you don't have enough
experience, then most likely any experts who look at your system will
be able to find a flaw. If this happens, it's your responsibility to
consider the flaw and learn from it, rather than just add one more
layer of complication and come back for another round.
A different way to get your cryptosystem reviewed is to have the NSA
look at it. A full discussion of this procedure is outside the scope
of this FAQ.
Among professionals, a common rule of thumb is that if you want to
design a cryptosystem, you have to have experience as a cryptanalyst.
------------------------------
** 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
******************************
