Cryptography-Digest Digest #173, Volume #14 Wed, 18 Apr 01 08:13:00 EDT
Contents:
Re: Reusing A One Time Pad (Tim Tyler)
Re: XOR TextBox Freeware: Very Lousy. (Bodo Eggert)
Re: Note on combining PRNGs with the method of Wichmann and Hill ("Brian Gladman")
Re: Reusing A One Time Pad (Tim Tyler)
Re: Reusing A One Time Pad (Tim Tyler)
Re: Reusing A One Time Pad (Tim Tyler)
Re: AES poll (Paul Crowley)
Re: HOW THE HELL DO I FIND "D"?!?! (Mats Kindahl)
Re: DES Optimizaton - Can Someone Explain? ("Kevin D. Kissell")
Proof of RSA (sianglin)
New to cryptography but in need of encryption ("Emmanuel Randon")
New to cryptography but in need of encryption :o) ("Emmanuel Randon")
Re: Proof of RSA (Mark Wooding)
Re: Reusing A One Time Pad ("Tom St Denis")
Re: Proof of RSA ("Tom St Denis")
Re: New to cryptography but in need of encryption (pjf)
Re: Note on combining PRNGs with the method of Wichmann and Hill (Mok-Kong Shen)
Re: Note on combining PRNGs with the method of Wichmann and Hill (Mok-Kong Shen)
Re: XOR_TextBox: Doesn't write to swap file if... (HiEv)
----------------------------------------------------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Reusing A One Time Pad
Reply-To: [EMAIL PROTECTED]
Date: Wed, 18 Apr 2001 07:57:43 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
: You have yet to prove that bijective compression is any more secure. In
: fact it's not. Let's demonstrate. [...]
You demonstration is unconvincing because your assertion is wrong:
"Bijective compression" is a term that covers a range of things.
Some of them are more secure than the compression used in PGP,
(simply through compressing better) and some of them are
less secure (simply through compressing less well).
--
__________
|im |yler Try my latest game - it rockz - http://rockz.co.uk/
------------------------------
From: Bodo Eggert <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto,alt.hacker
Subject: Re: XOR TextBox Freeware: Very Lousy.
Date: Wed, 18 Apr 2001 10:08:11 +0200
David Schwartz <[EMAIL PROTECTED]> wrote:
> the user. If the user had a good, secure means of sending the OTP to the
> recipient, why wouldn't he just use that mechanism to transfer the
> plaintext itself?
The trick is to transfer the random generator or the seed,
which allows to encrypt a certain (bigger) amount of plaintext.
1) Unfortunately, this requires a _good_ pseudo-random-generator.
2) there are other encryption methods allowing a bigger amount of
plaintext to be chiphered with the same key.
--
Linux forces a brain to configure
Windows forces a brain-damaged configuration
------------------------------
From: "Brian Gladman" <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers
Subject: Re: Note on combining PRNGs with the method of Wichmann and Hill
Date: Wed, 18 Apr 2001 09:26:04 +0100
"Brian Gladman" <[EMAIL PROTECTED]> wrote in message
news:N04D6.29202$I5.121674@stones...
> "Mok-Kong Shen" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
[snip]
A small correction to my last post - the Chi squared table values I quoted
were for 11 degrees of freedom when I should have quoted those for 10.
This makes no difference to the arguments in the post since the differences
are small.
For interest, the Chi-squared values for 100 buckets are:
mwc : 111 (A)
cong: 96 (B)
comb: 5950 (0.9 * A + 1.1 * B)
~100 is normal, ~6000 is abnormal beyond belief. The probability of the
result for comb being from a truly uniform PRNG would be considered to be
zero by any reasonable observer.
Brian Gladman
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Reusing A One Time Pad
Reply-To: [EMAIL PROTECTED]
Date: Wed, 18 Apr 2001 08:10:19 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
: "SCOTT19U.ZIP_GUY" <[EMAIL PROTECTED]> wrote:
:> It is well known for certain classes of files Huffman would be the
:> optimal. [...]
: There are no classes of files where huffman is optimal. [...]
I'd have to agree with David here.
Tom appears to be in need of a remedial compression class :-(
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Reusing A One Time Pad
Reply-To: [EMAIL PROTECTED]
Date: Wed, 18 Apr 2001 08:13:41 GMT
Mark G Wolf <[EMAIL PROTECTED]> wrote:
: I mean even if you used the same pad many times over a long period
: you'd have to assume that someone was actually collecting all your
: messages, which is not very likely.
Collecting some of your messages would normally be all that is required.
--
__________
|im |yler Try my latest game - it rockz - http://rockz.co.uk/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Reusing A One Time Pad
Reply-To: [EMAIL PROTECTED]
Date: Wed, 18 Apr 2001 08:15:37 GMT
Mark G Wolf <[EMAIL PROTECTED]> wrote:
:> Well, yes, if your threat model is "your kid sister", then yes, there's
:> nothing insecure about reusing your "OTP". But, then again, in that
:> scenario, there's nothing particularly insecure about ROT13 either...
: Your highly exaggerating.
Perhaps not - how old is your kid sister? ;-)
--
__________
|im |yler Rockz rulez - http://rockz.co.uk/
------------------------------
Subject: Re: AES poll
From: Paul Crowley <[EMAIL PROTECTED]>
Date: Wed, 18 Apr 2001 08:26:32 GMT
"Jack Lindso" <[EMAIL PROTECTED]> writes:
> From reading the government document concerning the choice of AES I had the
> feeling that Rijindael was selected without evident/sufficient proof for
> being the best choice.
With three excellent candidates to choose from it's hard to pick one
that's incontrovertibly the best.
--
__ Paul Crowley
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
------------------------------
Subject: Re: HOW THE HELL DO I FIND "D"?!?!
From: Mats Kindahl <[EMAIL PROTECTED]>
Date: 18 Apr 2001 10:46:28 +0200
"Dopefish" <[EMAIL PROTECTED]> writes:
> i know that but they do not exactly explain how to get this from the
> extended euclidian algorithm
It is a quite straightforward application of algebra...
For the equation ax + by = g, the Extended Euclidian Algorithm (EEA)
will find x, y, and g (= gcd(a,b)) given a and b.
So, we have e and n and want to find the multiplicative inverse of e
modulo n, let's call it d. More formally,
ed = 1 (mod n) (*)
By the definition of = (congruence) modulo n it follows that for the
equation to be satisfied, there has to be an integer k such that
ed + nk = 1
^ ^
+----+--- known
Now, by using EEA, we can find d and k (and g). If g != 1, then e is
not relative prime to n and there is no solution to (*), otherwise d
is the multiplicative inverse of e modulo n.
Hope this was helpful,
--
Mats Kindahl, IAR Systems, Sweden
Any opinions expressed are my own, not my company's.
------------------------------
From: "Kevin D. Kissell" <[EMAIL PROTECTED]>
Subject: Re: DES Optimizaton - Can Someone Explain?
Date: Wed, 18 Apr 2001 10:11:24 +0200
"John Savard" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> On Tue, 17 Apr 2001 22:23:30 +0200, "Kevin D. Kissell"
> <[EMAIL PROTECTED]> wrote, in part:
>
> >but I note that the permutated
> >S-box outputs in the source code in the Applied Cryptography
> >appendix (the "SPx" tables) do not seem to correspond to the
> >naive result of applying the P-permutation to the selected bits.
>
> Remember that the description of DES is big-endian. Also, the S-box
> entries may have been re-ordered; remember that the two bits selecting
> one of four permutations of the numbers 0 to 15 originally come one
> before and one after the four bits selecting which item in the
> permutation is used.
Thanks for the reply.
I noted the bit-numbering assumption, and the index transformation
necessary to treat the permutated S-box outputs as a linear array.
In any case, the discrepancy in results that I'm seeing does not
correspond to an endianness inversion nor to an index scrambling.
Each entry in my generated tables has the same number of bits
set as the corresponding entry that one finds in the text, but the bit
positions differ in a non-obvious way. I have subsequently found
that Schneier seems to have used Richard Outerbridge's "des3"
code as his model, so I will try to contact Outerbridge directly - unless
someone here posts the table generation algorithm first!
Kevin K.
------------------------------
From: sianglin <[EMAIL PROTECTED]>
Subject: Proof of RSA
Date: Wed, 18 Apr 2001 17:16:22 +0800
Can someone prove that, in RSA, D(E(M)) = M where M=message,
E=Encryption, D=Decryption?
------------------------------
From: "Emmanuel Randon" <[EMAIL PROTECTED]>
Subject: New to cryptography but in need of encryption
Date: Wed, 18 Apr 2001 11:54:12 +0200
I am developping for my "end of year" project, a network communication
software (Windows+VC ++).
Everything seems to be going fine. Only one part of the project is not clear
at all. We need to have an encryption capability in it.
We don't know a lot about cryptography. However we know we would like a
public algorithm encrypting the key of a private algorithm encrypting the
message.
Now the problem is that we don't have any idea of how to start that :o(
So if anyone can guide us a bit, it would be very nice !!!
Emmanuel.
------------------------------
From: "Emmanuel Randon" <[EMAIL PROTECTED]>
Subject: New to cryptography but in need of encryption :o)
Date: Wed, 18 Apr 2001 11:53:16 +0200
I am developping for my "end of year" project, a network communication
software (Windows+VC ++).
Everything seems to be going fine. Only one part of the project is not clear
at all. We need to have an encryption capability in it.
We don't know a lot about cryptography. However we know we would like a
public algorithm encrypting the key of a private algorithm encrypting the
message.
Now the problem is that we don't have any idea of how to start that :o(
So if anyone can guide us a bit, it would be very nice !!!
Emmanuel.
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Proof of RSA
Date: 18 Apr 2001 10:00:56 GMT
sianglin <[EMAIL PROTECTED]> wrote:
> Can someone prove that, in RSA, D(E(M)) = M where M=message,
> E=Encryption, D=Decryption?
Proposition
Given n = \prod_i p_i for distinct primes p_i, and e and d such that e
d = 1 (mod \lambda(n)), (x^e)^d = x (mod n) for all integers x.
Proof
(x^e)^d = x^{e d} (mod n). Considering this mod p_0, we see that
x^{e d} = x^{k(p_0-1)+1} = x (mod p_0) (due to a result by Fermat); by
symmetry the same holds mod the other p_i, and the proposition follows
from the Chinese Remainder Theorem.
-- [mdw]
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Reusing A One Time Pad
Date: Wed, 18 Apr 2001 10:04:25 GMT
"Tim Tyler" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> Tom St Denis <[EMAIL PROTECTED]> wrote:
> : "SCOTT19U.ZIP_GUY" <[EMAIL PROTECTED]> wrote:
>
> :> It is well known for certain classes of files Huffman would be the
> :> optimal. [...]
>
> : There are no classes of files where huffman is optimal. [...]
>
> I'd have to agree with David here.
>
> Tom appears to be in need of a remedial compression class :-(
Read my follow up.
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Proof of RSA
Date: Wed, 18 Apr 2001 10:06:13 GMT
"sianglin" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Can someone prove that, in RSA, D(E(M)) = M where M=message,
> E=Encryption, D=Decryption?
Yeah, read the 70's RSA paper.
Simply you get
D = (1/D) mod (p-1)(q-1)
The order of the group is at most lcm(p-1,q-1) which (p-1)(q-1) is a
multiple of. Therefore
(M^(E))^D mod pq is the same as M^(E*D mod (p-1)(q-1)) mod pq = M^(1) mod pq
= 1
Tom
------------------------------
From: [EMAIL PROTECTED] (pjf)
Subject: Re: New to cryptography but in need of encryption
Date: Wed, 18 Apr 2001 10:40:05 GMT
You could use the MS CryptoAPI (was it you who posted something
similar to the cryptoapi newsgroup) or you could use Crypto++, or one
of the other available APIs out there.
In two weeks, I should have completed Bletchley, my super friendly
interface (and documented) cross platform, open source, public domain
crypto API. RSA, SHA-1, and TwoFish, using the Yarrow PRNG under
Windows and Random under Linux/Free BSD. You could also use that.
-pjf
--
[EMAIL PROTECTED]
http://www.staticengine.com
Developer, KnowWonder Inc.
Musician, Static Engine
---
Digital Certificates provide no actual security for
electronic commerce; it's a complete sham.
-Bruce Schneier, Secrets & Lies
====== Posted via Newsfeeds.Com, Uncensored Usenet News ======
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
======= Over 80,000 Newsgroups = 16 Different Servers! ======
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers
Subject: Re: Note on combining PRNGs with the method of Wichmann and Hill
Date: Wed, 18 Apr 2001 13:16:24 +0200
Brian Gladman wrote:
>
> "Mok-Kong Shen" <[EMAIL PROTECTED]> wrote:
> >
> [snip]
> > > I am confident in this result without the need for a formal test but you
> are
> > > free to run one if you want to prove that my confidence is misplaced.
> >
> > Again sorry. I am not a statistician. I can trust the
> > methods stated in most statistical textbooks but can't
> > trust others. Chi-square test is also given in Knuth
> > vol. 2. The other method in question is Kolmogorow-
> > Smirnov. For the issue in point you have to use some
> > good real-life pseudo-random variables and do the test
> > in a manner recommended by the textbooks (in particular,
> > size of sample) and compare the results, once with all
> > factors 1.0 and once with deviated values, eventually
> > repeating the experiments an appropriate number of times.
> > (This is not any dis-appreciation of the value of your
> > method of testing uniformity. I would certainly be happy
> > to be among the first people to use it, if it has been
> > published in an article in a journal of statistics.
> > Until then, I can only accept results from methods
> > currently known in the literature, unfortunately.)
>
> There is nothing wrong or unscientific in the way I have presented the
> results. Plotting distributions based on a large number of trials is a well
> known, widely accepted and extensively documented practice. Moreover this
> technique is a basic technique that will be known to anyone who understands
> high school statistics.
>
> But I will indulge you just to show that it is silly it is to insist on a
> more sophisticated test for such an obviously non-uniform distribution.
>
> Firstly Knuth suggests that the recommended number of tests should be such
> that the expected number of entries in each category should be as large as
> possible but much larger larger than 5. In my tests this is 1,000,000 in
> each of 10 categories (buckets) - I hope you will accept that 1,000,000 is
> 'much larger than 5'.
>
> The Chi-squared result values (as in Knuth) for the three generators,
> measured against an expectation of a uniform distribution, are:
>
> mwc : 9.26 (A)
> cong: 11.28 (B)
> comb: 3991.00 (0.9 * A + 1.1 * B) mod 1.0
>
> For 10 categories the 50% and 75% confidence values are 9.3 and 12.5
> respectively, which suggests that there is nothing odd about the two basic
> PRNGs with values of 9 and 11. The comb PRNG gives a value of about 13 when
> the multipliers are both equal to 1.0, which is also in the normal range.
>
> But for the combined generator above, a uniform PRNG would only give a value
> of 36 or greater 0.01% of the time. And the probability (p) of a uniform
> random generator giving a value of 3990 is roughly 1/10^3500000 (plus or
> minus a few thousand powers of 10) - that is log10(1 / p) ~ 3.5 million.
>
> Hnece your confidence that I am wrong about the combined generator being
> very non-uniform will prove to be correct once in 10^3,500,000 trials. And
> I claim the remainder as justifying my position.
>
> No doubt you will now ask for another test since this Chi-squared result
> does not meet with your expectations.
No. In fact I personally don't like to apply Kolmogorov-
Smirnov. I almost invariably use chi-square. I never
exclude that any ideas of mine, in this thread or
elsewhere, anytime may turn out to be very wrong. Only
that I need to see clear proofs that I am wrong, proofs
that use commonly accepted methods. Now please present
your chi-square results in an easily understandable
way in conformance with common practice. Please use
confidence level of 0.95 or higher. I haven't seen any
tests in practice or textbook examples using 0.5 or
0.75. (A too low value means that one can barely trust
the significance of the result.) It is generally preferred
to have a larger number of categories rather than fewer
categories and large number of entries per categories,
as far as I am aware. (I remember to have read somewhere
about that for the chi-sqaure test.) With your sample size
of 10,000,000, using 100 categories or more would give
much better results, for we want to better (more finely)
examine the distribution. (I would think that a sample
size of 1,000,000 suffices.) Statisticians please correct
me, if I am wrong here. I believe that you have written a
program to do the test, so a repetition with such
modifications should be a very easy task. For the benefit
of the general readers, I like to request you to present
your results in a terse manner as follows:
(1) The generators used (parameters, seeds).
(2) Sample sizes.
(3) The number of catetories in the chi-square test.
(4) The multipliers used in the combinations investigated.
(The generators are to be tested individually, then
r1 + r2 mod 1, then c1*r1 + c2*r2 mod 1, with c1 and
c2 of your choise, employing several sets of values
of c1 and c2 with different magnitudes of deviations
from 1.0 to clearly demonstrate the existence of a
relationship between deviations from 1.0 and
uniformity/non-uniformity.)
(5) The chi-square statistics obtained.
(6) Your conclusion based on these statistics, establishing
your previous claim that, with c1 and c2 close to 1.0,
the combination is very non-uniform.
Thanks very much in advance.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers
Subject: Re: Note on combining PRNGs with the method of Wichmann and Hill
Date: Wed, 18 Apr 2001 13:30:23 +0200
Bryan Olson wrote:
>
> Mok-Kong Shen wrote:
> >
> > Mok-Kong Shen wrote:
> > >
> > > Bryan Olson wrote:
> > > >
> > > > Mok-Kong Shen wrote:
> > > >
> > > > >I like to add something to make my last paragraph better
> > > > >understandable: If one of the streams gets a factor 1.0
> > > > >(and it is uniform), isn't that everything is again
> > > > >(rigorously) theoretically o.k. in that particular issue?
> > > >
> > > > Of course not. The theorem was:
> > > > | as long as the streams are independent, if any of the
> > > > | streams are uniform then the sum is uniform.
> > >
> > > The PRNGs are assumed to be independent (I forgot to
> > > explictly say that) and uniform. Now one stream gets
> > > the factor 1.0, so that is uniform. The others are
> > > not uniform. So according to the theorem the modular
> > > sum is uniform, isn't it? (As I said elsewhere, the
> > > continuous case can be considered the limiting case
> > > of the discrete case, whose proof we have discussed
> > > sometime back. There is in fact a rigorous proof
> > > of the continuous case that doesn't use that limiting
> > > process. I found the paper oneday by chance in Math.
> > > Rev. but I unfortunately didn't note down the reference.)
> >
> > Addendum: The scheme of Wichmann and Hill is intended
> > to get a more uniform stream from a number of not well
> > uniform streams.
>
> And was not intended for cryptography. You now say the
> intentions contradict what you just said was assumed.
Did I ever say that Wichmann and Hill did their work
for purpose of cryptography? Their scheme intends
to get better pseudo-random number sequences. That
can be used to benefit in cryptography, for one can
use PRNGs in crypto. 'What' I said contradicts 'what'
I assumed?
>
> > The assumption I made above that
> > the PRNGs are uniform is for discussion of the
> > theoretical point you raised which I quote below:
> >
> > The modification destroys an important property of
> > the basic combination method: as long as the streams
> > are independent, if any of the streams are uniform
> > then the sum is uniform.
> >
> > So in that situation we assume that there are uniform
> > streams to start with.
>
> The theorem is a stronger result than you can establish with
> your scheme. The basic scheme has stronger properties too.
>
> > Note that we are actually doing splitting of hairs.
>
> No. You stated a bogus result. What evidence we have
> indicates that your it's false.
'What' is the bogus result? 'What' is the evidence?
Please say clearly with some details. Don't just use
categorical statements, leaving the reader(s) not knowing
what you have exactly in mind.
M. K. Shen
=================================
Was sich ueberhaupt sagen laesst, | Whatever can be said
laesst sich klar sagen; | can be clearly said;
und wovon man nicht reden kann, | and silence must be kept
darueber muss man schweigen. | on what one cannot tell.
|
Ludwig Wittgenstein | (a translation)
(1889 - 1951) |
------------------------------
From: HiEv <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto,alt.hacker
Subject: Re: XOR_TextBox: Doesn't write to swap file if...
Date: Wed, 18 Apr 2001 11:53:23 GMT
Anthony Stephen Szopa wrote:
>
> "Ryan M. McConahy" wrote:
[snip]
> > HELLO?!? You don't know much about crypto, do you? XOR is broken! Read
> > Applied Cryptography! I quoted it earlier, didn't I? It doesn't matter
> > wether or not it swaps to disk!
>
> Offer anyone in this news group $1000 if you cannot break their
> encrypted messages using XOR then.
Ok, let's say there is a theoretical situation where you could intercept
someone's XORed output so that you could attempt to crack it. Wouldn't
that situation also usually allow you to also get the OTP (One Time Pad,
the file that you use to encrypt your plaintext) that produced the
cypertext?
And if it doesn't, why wouldn't that person use the method that they are
using to send the OTP to send the cypertext?
Also, people don't usually send just one message like this, and multiple
messages make it easier to crack because they either always have to send
a new OTP or indicate to the receiving party what the OTP is, or they
reuse the same OTP, which is really dumb because then you've given away
your key. Many people will do this though, even though they've been
told not to, because it's easier than always choosing a new OTP.
Furthermore, your software doesn't bother to check for randomness or
long series of nulls. If I used XOR with a file I didn't realize had a
large section of nulls I could end up sending a chunk of my message in
plaintext!
You need to realize that an XORed file, by itself is useless to
everyone, including the intended receiver, the important part is the
OTP. If I want to send multiple encrypted files to a friend in, say
Germany, and the person who I want to receive this may not be the only
person who sees these messages, how am I supposed to hide what the OTP
is?
Your claim that someone would need to crack one XORed file to prove the
vulnerability of the system is ridiculous because it is an unrealistic
situation. If a person is using an encryption system and because
someone may be intercepting their messages then a public key system,
like PGP, is the way to go.
Tell you what though, you send me two XORed files encrypted with the
same OTP and I'll show you how to decrypt the shorter one entirely, the
same number of bytes of the longer one, and recover that much of the OTP
to boot! :-)
------------------------------
** 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
******************************
