Cryptography-Digest Digest #707
Cryptography-Digest Digest #707, Volume #13 Sun, 18 Feb 01 09:13:01 EST Contents: Cryptography FAQ (06/10: Public Key Cryptography) ([EMAIL PROTECTED]) Cryptography FAQ (07/10: Digital Signatures) ([EMAIL PROTECTED]) Crossposted-To: talk.politics.crypto,sci.answers,news.answers,talk.answers Subject: Cryptography FAQ (06/10: Public Key Cryptography) From: [EMAIL PROTECTED] Reply-To: [EMAIL PROTECTED] Date: 18 Feb 2001 13:56:41 GMT Archive-name: cryptography-faq/part06 Last-modified: 94/06/07 This is the sixth 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: 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?' 6.1. What is public-key cryptography? In a classic cryptosystem, we have encryption functions E_K and decryption functions D_K such that D_K(E_K(P)) = P for any plaintext P. In a public-key cryptosystem, E_K can be easily computed from some ``public key'' X which in turn is computed from K. X is published, so that anyone can encrypt messages. If decryption D_K cannot be easily computed from public key X without knowledge of private key K, but readily with knowledge of K, then only the person who generated K can decrypt messages. That's the essence of public-key cryptography, introduced by Diffie and Hellman in 1976. This document describes only the rudiments of public key cryptography. There is an extensive literature on security models for public-key cryptography, applications of public-key cryptography, other applications of the mathematical technology behind public-key cryptography, and so on; consult the references at the end for more refined and thorough presentations. 6.2. How does public-key cryptography solve cryptography's Catch-22? In a classic cryptosystem, if you want your friends to be able to send secret messages to you, you have to make sure nobody other than them sees the key K. In a public-key cryptosystem, you just publish X, and you don't have to worry about spies. Hence public key cryptography `solves' one of the most vexing problems of all prior cryptography: the necessity of establishing a secure channel for the exchange of the key. To establish a secure channel one uses cryptography, but private key cryptography requires a secure channel! In resolving the dilemma, public key cryptography has been considered by many to be a `revolutionary technology,' representing a breakthrough that makes routine communication encryption practical and potentially ubiquitous. 6.3. What is the role of the `trapdoor function' in public key schemes? Intrinsic to public key cryptography is a `trapdoor function' D_K with the properties that computation in one direction (encryption, E_K) is easy and in the other is virtually impossible (attack, determining P from encryption E_K(P) and public key X). Furthermore, it has the special property that the reversal of the computation (decryption, D_K) is again tractable if the private key K is known. 6.4. What is the role of the `session key' in public key schemes? In virtually all public key systems, the encryption and decryption times are very lengthy compared to other block-oriented algorithms such as DES for equivalent data sizes. Therefore in most implementations of public-key systems, a temporary, random `session key' of much smaller length than the message is generated for each message and alone encrypted by the public key algorithm. The message is actually encrypted using a faster private key algorithm with the session key. At the receiver side, the session key is decrypted using the public-key algorithms and the recovered `plaintext' key is used to decrypt the message. The session key approach blurs the distinction between `keys'
Cryptography-Digest Digest #707
Cryptography-Digest Digest #707, Volume #12 Mon, 18 Sep 00 10:13:01 EDT
Contents:
Re: Chosen and known attacks - are they possible ?? (David Blackman)
Encryption Algorithms for 3GPP Security (Andrew Poh)
Re: wince encryption algorithm (Runu Knips)
Re: QUESTION ABOUT ALGORITHMS (Runu Knips)
Rik Kershaw-Moore/Intl/Herman Miller is out of the office. ("Rik Kershaw-Moore")
Re: QUESTION ABOUT ALGORITHMS (Runu Knips)
Re: Double Encryption Illegal? (Runu Knips)
Re: another nonlinear decorrelation idea (Runu Knips)
Questions about how to run a contest (Sylvain Martinez)
Re: Chosen and known attacks - are they possible ?? ([EMAIL PROTECTED])
Web-based archaeology course (Mikey)
Hamming weight ("kihdip")
Re: Chosen and known attacks - are they possible ?? (Guy Macon)
Re: Questions about how to run a contest ("kihdip")
Re: MIRACL (Soeren Gammelmark)
Re: Algebra, or are all block ciphers in trouble? (Mack)
Re: Hamming weight (Mack)
Re: Questions about how to run a contest (Mack)
Re: Chosen and known attacks - are they possible ?? ("kihdip")
From: David Blackman <[EMAIL PROTECTED]>
Subject: Re: Chosen and known attacks - are they possible ??
Date: Mon, 18 Sep 2000 22:14:03 +1100
kihdip wrote:
>
> In 'Communications Security for the Twenty-first Century: The Advanced
> Encryption Standard' Susan Landau explains different attack models.
> <http://www.ams.org/notices/24/fea-landau.pdf>
>
> The models are frequently used to describe an attack form:
> - Ciphertext only
> - Known plaintext
> - Chosen plaintext
> - Chosen ciphertext
>
> Forgive my ignorance, but are the known and chosen attacks only teoretical
> ?? If not: How would an attacker get a chosen plaintext encrypted ??
> (His goal is to find the key, so obviously he cannot encrypt the plaintext
> himself)
>
> Kim
Known plaintext can come up.
In many cases, standard predictable messages of some sort will be sent
using the same key as seriously secret messages. In those cases, you
often know or can guess at least small amounts of plaintext.
For instance known plaintext played a part in the British cracks of
various German cyphers in WW2. The British knew or guessed that the
Germans broadcast encrypted weather forecasts each morning on navy
radio. The same encryption method and key were used for additional
transmissions later in the day, some of them being much more secret and
important. The British had about as much idea of the weather as the
Germans did, and because the German weather forecasts were in a very
standardised format, the British could often guess exactly what the
plaintext for the weather forecast was, and then crack the cypher to get
the key of the day.
Another possibility is the attacker has bugged department A of an
organisation and knows what they are sending, but hasn't managed to bug
department B. A and B use the same cypher and key for outside
communications.
Chosen plaintext seems unlikely, but it can happen in some applications.
Imagine a communication service provider sends all messages for their
clients from point to point using an encrypted link. Attacker is
wondering what some of the client messages are. Attacker buys a contract
with the service provider, taps the encrypted communication line (it's
easy to tap, that's why the provider bothers to encrypt it :-), and
sends all the chosen plaintext they like.
Chosen cyphertext seems even more unlikely, but i can imagine some
situations where even this might happen.
Good modern cyphers attempt to be secure even if the attacker has
obtained enormous amounts of known plaintext, chosen plaintext, or
chosen cyphertext. Loki 97 was dropped from the AES competition because
Rijmen and Knudsen found a way to crack it with about 2 to the power of
56 blocks of known plaintext (that's millions of full hard discs).
--
From: Andrew Poh <[EMAIL PROTECTED]>
Subject: Encryption Algorithms for 3GPP Security
Date: Mon, 18 Sep 2000 18:55:39 +0800
I am new to this newsgroup, so kindly forgive me if this question
has been posted and answered before in the past.
Basically, I am interested to know if there any any information
or pointers to the f1, f2, f3, f4, f5 function in the 3GPP Technical
Specs
TS 33.102.
The exact algorithm is not specified in the standards and I believe
it will be up to the implementors to come up with the algorithm.
However, I wish to know what are the possible algorithms that
others may have encountered which satisfy the requirements
given in the standards.
I am aware of the Confidentiality Algorithm f8 and the Integrity
Algorithm f9, which is based on the KASUMI algorithm.
I would appreciate any information or feedback you may have.
Kindly CC all r
Cryptography-Digest Digest #707
Cryptography-Digest Digest #707, Volume #11 Thu, 4 May 00 22:13:01 EDT Contents: Re: Silly way of generating randm numbers? (stanislav shalunov) Re: RC5 math (David Hopwood) Re: How Extend RMI Security System to handle Delegation (David Hopwood) Re: GPS encryption turned off (Paul Rubin) Re: Fixed: Sboxgen tool (Tim Tyler) Re: GPS encryption turned off (Roger Schlafly) Re: KRYPTOS Something new ? (Tom Knight) Re: Fixed: Sboxgen tool (Terry Ritter) Re: The Illusion of Security (Tim Tyler) Re: GPS encryption turned off (Paul Schlyter) Re: The Illusion of Security (Tim Tyler) Re: U-571 movie (OT) (William Rowden) Re: Fixed: Sboxgen tool (Tom St Denis) Re: GPS encryption turned off (Paul Rubin) Crossposted-To: sci.math Subject: Re: Silly way of generating randm numbers? From: stanislav shalunov <[EMAIL PROTECTED]> Date: Thu, 04 May 2000 22:17:07 GMT Richard Heathfield <[EMAIL PROTECTED]> writes: > As far as I'm aware, pi passes all mathematical tests for randomness. Not Kolmogorov's algorithmic complexity test. (Kolmogorov complexity of pi is O(1)). -- stanislav shalunov | Speaking only for myself. -- Date: Thu, 04 May 2000 02:42:06 +0100 From: David Hopwood <[EMAIL PROTECTED]> Reply-To: [EMAIL PROTECTED] Subject: Re: RC5 math =BEGIN PGP SIGNED MESSAGE= Richard Parker wrote: > > <[EMAIL PROTECTED]> wrote: > > Is there a paper available that describes RC5 in mathematical terms > > including analysis of its strength? > > The RC5 encryption algorithm was written by Ronald L. Rivest, who is one of > the original founders of RSA <http://www.rsalabs.com/>. Information about > his cipher designs can generally be founds on the RSA website. The first > published paper in which Rivest described RC5 is available from RSA: > > R.L. Rivest, "The RC5 encryption algorithm, "Proceedings of the > 2nd Workshop on Fast Software Encryption, Springer-Verlag, 1995, > pp. 86-96. > <ftp://ftp.rsasecurity.com/pub/rsalabs/rc5/rc5.ps> A slightly revised 1997 version of this is at http://theory.lcs.mit.edu/~rivest/rc5rev.ps; the changes are at http://theory.lcs.mit.edu/~rivest/rc5rev.txt RC5 is also described in an RFC: Ron Rivest, "The RC5, RC5-CBC, RC5-CBC-Pad, and RC5-CTS Algorithms," RFC 2040, October 1996. > A good overview of the analysis that has been done on RC5 has also been > prepared by RSA: > > B.S. Kaliski Jr. and Y.L. Yin, "On the Security of the RC5 > Encryption Algorithm," RSA Laboratories Technical Report TR-602, > 1998. > <ftp://ftp.rsasecurity.com/pub/rsalabs/rc5/rc5-report.pdf> > > The best known attack on RC5 is differential cryptanalysis, and the best > published differential cryptanalysis of RC5 is by Knudsen and Meier: > > L.R. Knudsen and W. Meier, "Improved differential attack on RC5," > Advances in Cryptology, Proceedings of Crypto'96, LNCS 1109, > Springer-Verlag, 1996, pp. 216-228. > <ftp://ftp.esat.kuleuven.ac.be/%2Fpub/COSIC/knudsen/rc5.ps.Z> An earlier paper was: B.S. Kaliski, Y.L. Yin, "On Differential and Linear Cryptanalysis of the RC5 Encryption Algorithm", Advances in Cryptology - CRYPTO '95, pp. 171-184. Springer-Verlag, 1995. and some more recent ones are: H. Heys, "Linearly Weak Keys of RC5," IEE Electronics Letters, vol. 33, no. 10, pp. 836-838, 1997. http://www.engr.mun.ca/~howard/PAPERS/rc5_letter.ps A. Biryukov, E. Kushilevitz, "Improved Cryptanalysis of RC5," Advances in Cryptology - EuroCrypt '98. http://www.cs.technion.ac.il/~eyalk/alex.ps.Z A. A. Selcuk, "New results in linear cryptanalysis of RC5," Fast Software Encryption - Fifth International Workshop, Paris, France, LNCS. Springer-Verlag, 1998. H. Handschuh, "A Timing Attack on RC5," Workshop on Selected Areas in Cryptography - SAC '98, Queen's University, Kingston, Ontario, Aug. 1998. To be published by Springer-Verlag. http://www.enst.fr/~handschu/rc5.ps H. Heys, "A Timing Attack on RC5," Workshop on Selected Areas in Cryptography - SAC '98, Queen's University, Kingston, Ontario, Aug. 1998. To be published by Springer-Verlag. http://www.engr.mun.ca/~howard/PAPERS/rc5_timing.ps Takeshi Shimoyama, Kiyofumi Takeuchi, Juri Hayakawa, "Correlation Attack to the Block Cipher RC5 and the Simplified Variants of RC6," Presented at the 3rd AES Candidate Conference. http://csrc.nist.gov/encryption/aes/round2/conf3/papers/36-tshimoyama.pdf There are similar lists of
Cryptography-Digest Digest #707
Cryptography-Digest Digest #707, Volume #10 Thu, 9 Dec 99 00:13:02 EST Contents: Re: NSA should do a cryptoanalysis of AES (Tim Tyler) Re: Synchronised random number generation for one-time pads (Tim Tyler) Re: Synchronised random number generation for one-time pads (Tim Tyler) Re: NSA future role? (CLSV) Re: AES Randomness Testing (Tim Tyler) Re: MMPC - A multi-message encryption algorithm (Jim Shapiro) Re: If you're in Australia, the government has the ability to modify your files. >> 4.Dec.1999 (Greg) weak algorithm, too hard for me (Gaccm) Re: NSA future role? (SCOTT19U.ZIP_GUY) Re: NSA future role? (Steve K) SRP - a secure alternative for authentication >> Nice reading ... ([EMAIL PROTECTED]) From: Tim Tyler <[EMAIL PROTECTED]> Subject: Re: NSA should do a cryptoanalysis of AES Reply-To: [EMAIL PROTECTED] Date: Thu, 9 Dec 1999 00:28:29 GMT Douglas A. Gwyn <[EMAIL PROTECTED]> wrote: : Tim Tyler wrote: [DES] :> Really? : Yes. I feel you need some quotation treatment ;-) In discussing the strength of DES, Bruce Schneier wrote in "Applied Cryptography": ``A brute force DES-cracking machine that can find a key in an average of 3.5 hours cost only $1 Million in 1993. DES is so widespread that it is naive to pretend that the NSA and its counterparts haven't built such a machine.'' ...and... ``Winn Schwartau writes that the NSA had built a massively parallel DES-cracking machine as early as the mid-1980s. At least one such machine was built [...] Supposedly there are a series of algorithms that can reduce the complexity of a DES brute-force search by several orders of magnitude. Contextual algorithms, based on the inner workings of DES, can scrap sets of possible keys based on partial solutions. Statistical algorithms reduce this effective key size still further. And other algorithms choose likely keys - words, printable ASCII, and so on [...] - to test. The rumour is that the NSA can crack DES in 3 to 15 minutes, depending on how much preprocessing they can do. And these machines cost only $50,000 each, in quantity.'' As for expected lifespan: DES was adopted as a federal standatd in 1976. It became an ANSI standard in 1981. The terms of the DES standard stipulate it be reviewed every five years. It was renewed in the 1983 review. It was renewed again in 1987 - and *again* in 1992. DES did not outlive its expected life - from the perspective of the 1992 review, anyway. It was almost certainly cracked, probably easily and en-masse while it was still in service as an officially endorsed US government standard. -- __ |im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED] It's been lovely, but I have to scream now. -- From: Tim Tyler <[EMAIL PROTECTED]> Subject: Re: Synchronised random number generation for one-time pads Reply-To: [EMAIL PROTECTED] Date: Thu, 9 Dec 1999 00:37:53 GMT amadeus wrote: : OTP is totally secure given it is properly used. The problems are key : distribution and key cancellation/deletion. [...] Then there's the issue that a known-plaintext attack reveals the key - and possibly allows inauthentic messages to be passed off as the real one. Authenticity is a problem for OTPs. With your typical block cypher, knowing the plaintext does *not* instantly reveal the message key, and allow forged message(s) to be sent. -- __ |im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED] Love is chemistry; sex is physics. -- From: Tim Tyler <[EMAIL PROTECTED]> Subject: Re: Synchronised random number generation for one-time pads Reply-To: [EMAIL PROTECTED] Date: Thu, 9 Dec 1999 00:42:30 GMT Scott Nelson <[EMAIL PROTECTED]> wrote: : It's quite conceivable that OTP technology : of the near future could be used to send _video_ messages. No doubt it *could* be done today. However - for most applications - I'm sure that there must be better ways of doing things than this. OTPs face the key-distribution problem more strongly than any other type of cypher. -- __ |im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED] It's not enough to succeed - others must fail. -- From: CLSV <[EMAIL PROTECTED]> Subject: Re: NSA future role? Date: Thu, 09 Dec 1999 01:19:45 + albert wrote: >>> If you walk into the library of the University of Michigan, you can actually find >>> all you need to know as far as how to make a nuclear bomb. CLSV wrote: >> One of those myths started by popular science magazines. JCA wrote: > Actually, it is true. However, you are right in that popular science magazines > have been responsible for misl
Cryptography-Digest Digest #707
Cryptography-Digest Digest #707, Volume #9 Sat, 12 Jun 99 18:13:04 EDT Contents: Re: Caotic function ([EMAIL PROTECTED]) Re: OTP is it really ugly to use or not? ([EMAIL PROTECTED]) Re: Slide Attack on Scott19u.zip ([EMAIL PROTECTED]) Yet another simplecipher (YASC) ([EMAIL PROTECTED]) Another free email? ([EMAIL PROTECTED]) Re: RSA example with small numbers ([EMAIL PROTECTED]) Re: RSA example with small numbers (James Pate Williams, Jr.) Re: OTP is it really ugly to use or not? (Jerry Coffin) Re: differential cryptanalysis ([EMAIL PROTECTED]) Re: Random numbers on a sphere (Virgil) From: [EMAIL PROTECTED] Subject: Re: Caotic function Date: Sat, 12 Jun 1999 20:29:05 GMT Uhm... most Chaotic functions use i ( i-Sqrt(-1) ), in imaginary no. ( or rather i+n, a complex no), so are v.difficult to implement easily. Take a starting point C_0 in the plane of coordinates u_0 and v_0. Fron the coordinate of C_0 form a second point C_1, of coordinates u_1=(u_0)^2 -(v_0)^2 + u_0 and v_1=2((u_0)(v_0))+v_0 etc i.e.: u_k=(u_k-1)^2 - (v_k-1)^2 +u_0 v_k=2((u_k-1)(v_k-1))+v_0 where x_n = x subscript n (ie the nth x), and x^n = x to the power n. a point C of coordinates u and v - u+iv (where iv is the imaginary number iv) of course there are many other ways, but that should do for a paper at college... if you need to _understand_, buy a good book, talk to people cleverer than me,, etc etc... [EMAIL PROTECTED] -- From: [EMAIL PROTECTED] Subject: Re: OTP is it really ugly to use or not? Date: Sat, 12 Jun 1999 19:35:04 GMT In article <[EMAIL PROTECTED]>, Cyba Nonymous <[EMAIL PROTECTED]> wrote: > I read in this group that the security of an OTP depends on the > pad being random. Really random and not just pseudo-random. OK so > let's say that I buy that for the moment. You should. If you can predict a OTP what's the point? > I can see how OTP security works because any message can be > decoded into every possible message of its length using some > "key". So brute force can never work on an OTP because you > will get every possible message in the process and that gets you > nowhere. If the key is truly random it doesn't matter of the plaintext. > Ok that brings me to my first question which is even if the pad > is not random it still seems to me that the message will decode > into just as many messages with just as many keys? Yes? No? The pad must be random. If it can predicted then others can read the message. > And, if it is true (which is possible because I am a dummy) then > why can't I exploit that and encrypt a (fake) message with a non random > key to get a stream of ciphered text and then derive another key that > gives me another message (the real one)? Now the mystery > math will give the cracker the "wrong" message..right? I could > go on and on but I think you experts will see the point I am trying to > make and point out the error of my thinking. With the OTP you could send all zeros as the ciphertext and have the key as the message (which would be ironic). The security comes from the fact that no plaintext is 'righter' then any other. In block ciphers you can detect keys which work more often then others (i.e 'righter'). In a OTP the key is used once. > The other thing that pops into my mind is random versus repeating. If it repeats it is not a OTP. for example 'abcabcabcabcabc' is predictable thus not random. Random doesn't always equal random as random numbers do not exist. If you cannot predict it with any means faster then guessing it (brute force) then it's considered random. > Oh yeah and what if I took a video CD and scrambled it and then > if I took another video CD and scrambled it. And, then I scrambled > the two of them together. And, then I used that CD with the program > above to generate these temporary pads from codewords. How would > you rate the ability of someone to crack a particular message using this > OTP method? Easy, Moderate, Hard, Very Hard, Impossible ? Well using video CDs is a bad idea. I could accidently buy one of them and accidently crack your messages. IF you made the video yourself hmm, ok... But usually there are headers etc.. So I would avoid that. > I am real curious to hear the feedback. Look, and I already know > I am a dummy so please temper your scorn. Thanks. Nope no problem. Tom -- PGP public keys. SPARE key is for daily work, WORK key is for published work. The spare is at 'http://members.tripod.com/~tomstdenis/key_s.pgp'. Work key is at 'http://members.tripod.com/~tomstdenis/key.pgp'. Try SPARE first! Sent via Deja.com http://www.deja.com/ Share what you know. Learn what you don't.
