Cryptography-Digest Digest #776, Volume #12 Tue, 26 Sep 00 04:13:00 EDT
Contents:
Re: A Different Kind of Quantum Computer (SCOTT19U.ZIP_GUY)
Re: Tying Up Loose Ends - Correction (SCOTT19U.ZIP_GUY)
Re: Question on biases in random numbers & decompression (SCOTT19U.ZIP_GUY)
Re: NTRU question (actually truncated modular polynomial question) (Scott Contini)
Re: Tying Up Loose Ends - Correction (Guy Macon)
Re: Encryption Project ("kihdip")
Test for weak keys in 3DES ("kihdip")
Re: On block encrpytion processing with intermediate permutations (Bryan Olson)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: A Different Kind of Quantum Computer
Date: 26 Sep 2000 03:46:00 GMT
[EMAIL PROTECTED] (John Savard) wrote in
<[EMAIL PROTECTED]>:
>On Mon, 25 Sep 2000 15:37:42 -0700, "A. Melon"
><[EMAIL PROTECTED]> almost wrote, in part:
>
>>Quantum computers can only solve problems in BQP, which is not thought
>>to include NP-complete problems. Now there is a new type of quantum
>>computer being proposed:
>
>>http://xxx.lanl.gov/abs/quant-ph/9910073
>
>>The paper claims this could solve NP-complete and sharp-P-complete
>>problems.
>
>>No, this isnt the End Of Cryptography As We Know It (EOCAWKI). Even if
>>the claims are true, it may be impossible to actually build. Even if
>>it is possible to build, it will be easy to make ciphers that defeat
>>it.
>
>>For example, make a random, public, invertible, 27x27 sbox, and
>>distribute it on CD-ROM. Encrypt a block by applying AES, then passing
>>it through the sbox (in groups of 27 bits), then applying AES again.
>>The sbox is only 432MB, so it is easy to distribute.
>
>Oh, dear. I have visions Scott27u now.
>
Well actually I know I did 4 8 16 and then 19.
I am quite happy with prime numbers for the future
ones so lets wait a few years till floppies
commonly hold several gigs and leap to scott29u
>>The quantum computer
>>would need millions of qbits to crack it.
>
>I wonder. There might be a meet-in-the-middle attack. Because the
>quantum computer's copy of the CD-ROM would *not* have to be in qbits,
>since the CD-ROM is fixed and public; the number of qbits only has to
>be the length of the secret key. But the non-qbit size of the problem
>might still create problems in avoiding decoherence or something.
>
Your correct John you have been reading more than Enigma
that is what I haver read also. Most systems to be modeled you
need only enough qbits to match the key length. But since most
still don't believe quantum computers exist. You may be wasting
your time telling those in this group.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website **now all allowed**
http://members.xoom.com/ecil/index.htm
Scott LATEST UPDATED source for scott*u.zip
http://radiusnet.net/crypto/ then look for
sub directory scott after pressing CRYPTO
Scott famous Compression Page
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
I leave you with this final thought from President Bill Clinton:
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Tying Up Loose Ends - Correction
Date: 26 Sep 2000 04:00:43 GMT
[EMAIL PROTECTED] (Tim Tyler) wrote in <[EMAIL PROTECTED]>:
>Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
>
>: BTW, could you answer my question of whether Scott's
>: 1-1 scheme can deal with arbitrary boundaries, since
>: you are apparently fairly familiar with that?
>
>I believe David found that Matt Timmerman's scheme could be simply
>adapted to allow for abritrary block boundaries. IIRC David advised
>Matt of this, and Matt implemented it. I might be making all this up,
>though ;-|
>
>Anyway, on http://members.nbci.com/ecil/compres5.htm David has code that
>bijectively goes to and from Matt's finitely odd files - i.e. binary
>strings that end with a 1 followed by an infinite zero tail.
>
>The code...
>Converts to/from files made of any number of bytes;
>Converts to/from even byte length files;
>Converts to/from odd byte length files;
>Converts to/from 8 bytes multiple file.
>
>I don't know if David's used other types of granularity. I figure he
>knows how to do it if he wants to.
>
>His original compression programs only worked with byte-oriented files.
>I don't know if this has changed since I last looked at them.
>
>You could probably chain their output through the "finitely odd"
>convertors, if you wanted other types of granularity.
Your correct Tim. Thanks for anwsering Mok. I guess he is not the
kind of person I can communicate with so I think its best I stop answering
his posts. We never get anywhere I am left with the feeling that he never
gets any closer to understanding what I have done. I think Matt got his
idea of file endings from my huffman endings. But his is different and
there seems to be several ways to look at the problem. Even the DSC
program has at its heart the file end optimizations that Matt used in
his arithmetic coding endings. I was wondering if anyone has written
a DSC type of program for BTW or such before to make the opitmal blending
of the pointer to a string. I really don't know how to search the net
for such a thing since I am not really sure what one would call it.
But there are several possible aplications in compression and
enctyption where one can use such methods. So you'd think they
would be covered in text books. But I haven't seen it yet.
The main trick in DSC is to have a internal file not of 8 bits
but of 8 9 9 8 9 8 8 8 9 8 8 ...
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website **now all allowed**
http://members.xoom.com/ecil/index.htm
Scott LATEST UPDATED source for scott*u.zip
http://radiusnet.net/crypto/ then look for
sub directory scott after pressing CRYPTO
Scott famous Compression Page
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
I leave you with this final thought from President Bill Clinton:
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Crossposted-To: com.compression
Subject: Re: Question on biases in random numbers & decompression
Date: 26 Sep 2000 04:13:33 GMT
[EMAIL PROTECTED] (Benjamin Goldberg) wrote in
<[EMAIL PROTECTED]>:
>SCOTT19U.ZIP_GUY wrote:
>>
>> [EMAIL PROTECTED] (Tim Tyler) wrote in <[EMAIL PROTECTED]>:
>>
>> >Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
>> >
>> >: I've GOT a random bitstream, which means random 0s and 1s. What I
>> >: want from this get random 0s, 1s, and 2s. I want the arithmetic
>> >: encoder to convert from one form to the other.
>> >
>> >: Since I think that if I were *starting out* with random
>> >: (equiprobable) 0s, 1s, and 2s, and *en*coded them with an
>> >: arithmetic coder, I *should* get a random bitstream (with 0 and 1
>> >: equiprobable), I think that using an arithmetic *de*coder on a
>> >: random bitstream should let me producde random 0s, 1s, and 2s.
>> >
>> >: The reason I want to try this, is that if I take my random
>> >: bitstream, and take two bits at a time, getting a number in the
>> >: range 0, 1, 2, 3, and discard all 3s to get a number in the desired
>> >: (0, 1, 2) range, I'm WASTING 25% of my random bits, AND I might end
>> >: up taking an arbitrarily long time to get a single trit. Bleh.
>> >: [...]
>> >
>> >It sounds like using arithemetic decompression routine will do
>> >much of what you want.
>> >
>> >I think you will find you might still wind up taking an arbitrarily
>> >long time to get a single trit, though - I don't think there's any
>> >way around that without introducing bias.
>> >
>> >I suspect that your arithmetic compressor will need access to an
>> >unbounded quantity of RAM as well in order to be guaranteed to
>> >operate correctly.
>> >
>> >In all, the idea sounds a bit like converting a binary number to base
>> >3 (or base n), with the MSBs coming first.
>> >
>> >If thinking about it this way, consider treating the stream as binary
>> >and tertiary (or n-ary) expansions of real numbers between zero and
>> >one.
>>
>> This is ture you have to make some trade off if you want to get
>> exactly a random 33% chance at each symbol. You can as I sugguest
>> take 2 bits. and use only the first 3 states tossinge the fourth
>> state.
>
>Everyone seems to be telling me to take two bits and discard the value
>3, and COMPLETELY ignoring the fact that I want to discard as little of
>the bitstream as possible.
>
>> Or if you want take 4 bits. then you have 16 states. You can assign
>> 15 of them easily since 3*5 = 15 put toss the 16th state and get 4
>> bits more.
>
>Hmm:
>Method a: use 2 bits at a time, discard 25% of bitstream.
>3 trits uses 3*2 bits minimum, 4*2 bits on average.
>Method b: use 4 bits at a time, discard 6.25% of bitstream.
>3 trits uses 3*4 bits minimum, more on average (but I'm not going to
>bother to calculate how much more).
>
>Since I want to discard as little of the stream as possible, why the
>HELL would I want to use method b?
>
>> Using an arithmetic coder involves these kind of trade offs
>> if you need exactly 33% likelyhood from each symbol. If you don't want
>> 33% random but want close use an arithmetic coder where one symbol
>> slightly heaver than the other 2. And when the heaver symbol comes up
>> shift the weight of it so the next symbol weighs more. This way you
>> can get close to 33% random and you don't have to wait forever to get
>> a symbol out.
>
>Ugh. That sounds like an especially stupid statement, even for you. I
>said I wanted 33% each, and you're telling me how to get something other
>than 33% each. I AM willing to take an arbitrarily long time (and use
>an arbitrarily large amount of memory) to get a symbol.
>
>> To do this with 2 bit pairs. Assign "0" to 00 "1" to 01 "2" to 10 and
>> 11 when a two comes up assign the 11 to symbol "1" you can to this
>> with more bits but thought I would explain the idea. You could
>> also leave the 11 assigned to the value it was last shifted too
>> that when whenever you restart the program you wont get a biasis
>> for the first trit being a "2" in case some one is analysising
>> the ouputs.
>>
>> David A. Scott
>
>Obviously you have trouble reading, or perhaps memory problems, since I
>said, way back at the start of the thread <sarcasm>TWO whole messages
>ago</sarcasm>:
>
Actually I do remember. I was the first one to suggest taking 2 bits
and using 3 states to get the three valuse and toss the fourth state.
You seemed to be confused by it. And others pointed out that if the
string was random this would get you the varibles in the truely randum
rate you wanted. You seemed not to like that. Well as explained you either
waste some bits and don't get exactly the random nature of the bits you
so desire. Or use all the bits at don't get the rate. THe choice is yours.
I know would suggest you use the first one anything else would add more
confusion. Sorry I tried to explain other trade offs for you since it
has done nothing but confuse you more. Are you related to Mok?
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website **now all allowed**
http://members.xoom.com/ecil/index.htm
Scott LATEST UPDATED source for scott*u.zip
http://radiusnet.net/crypto/ then look for
sub directory scott after pressing CRYPTO
Scott famous Compression Page
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
I leave you with this final thought from President Bill Clinton:
------------------------------
From: [EMAIL PROTECTED] (Scott Contini)
Subject: Re: NTRU question (actually truncated modular polynomial question)
Date: 26 Sep 2000 04:54:45 GMT
In article <[EMAIL PROTECTED]>,
Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
>NTRU uses truncated modular polynomials as it's primary objects.
>I understand how multiplication and addition work, but I do not
>understand how inversion works... I can't seem to understand the stuff
>on ntru's web site.
>
>For those who don't want to bother to visit the web site, here are the
>addition and multiplication operations:
>
>Definitions:
>N : the number of terms; the order of the poly is N-1.
>m : the modulo
>% : modular reduction; x = y % m results in values 0..(m-1)
>x_i : the ith term of x.
>
>To calculate c = a + b % m
>for( i = 0 .. N-1 ) c_i = a_i + b_i % m
>
>To calculate c = a * b % m
>for( i = 0 .. N-1 ) c_i = sum(j=0..N-1, a_j * b_((i-j)%N) ) % m
>
>Assuming that the multiplicative inverse function is modinv( a, m ),
>I know that if m = x*y (where gcd(x,y)=1), then
> modinv(a, m) = modinv(a, x) * modinv(a, y)
>And I think I can can even figure out how to get modinv( a, x**n ) where
>x is prime, if I already have modinv( a, x )...
>But how do I get modinv( a, x )???
>
>An equivilant question seems to be, how do I do long division for
>truncated modular polynomials?
>
>If someone could post clear psuedocode or C code, it would be much
>appreciated... (clearer than the stuff on NTRU's web site, that is)
>
There is a document that you can download from NTRU's web site that
explains this, though it has a few typo's in it. Below is my Magma
code for inverses modulo X^N - 1 where the polynomials are taken
modulo p . R is the ring, a is the polynomial that you
want to compute inverses for, etc... For more information on my code,
you can download the document "Magma for crypto applications" which
gives an example of using Magma to do NTRU. The document is available
from my web page:
http://www.maths.usyd.edu.au:8000/u/contini/
Scott
========================================================================
function InverseModPrime( R, a, p, N )
X := R.1;
Rp := PolynomialRing( GF(p) );
k := 0; b := R!1; c := R!0;
f := a; g := X^N - 1;
while true do
f0 := Evaluate(f, 0);
while f0 eq 0 do
f := f div X; c := c * X; k +:= 1;
f0 := Evaluate(f, 0);
end while;
if Degree(f) eq 0 then
b := R!Rp!(b * Modinv( f0, p ));
ans := b*X^(-k mod N) mod (X^N-1);
break;
end if;
if Degree( f ) lt Degree( g ) then
t := f; f := g; g := t;
t := b; b := c; c := t;
end if;
f0 := Evaluate(f, 0);
g0 := Evaluate(g, 0);
u := (Modinv( g0, p ) * f0) mod p;
f := R!Rp!(f - u*g);
b := R!Rp!(b - u*c);
end while;
return ans;
end function;
function InverseModPrimePower( R, a, prime_power, N )
fact := Factorisation( prime_power );
ok, p, r := IsPrimePower( prime_power );
if ok eq false then
print "ERROR: function requires prime power";
return 0;
end if;
b := InverseModPrime( R, a, p, N );
q := p;
X := R.1;
while q lt prime_power do
q := q*p;
Rq := PolynomialRing( ResidueClassRing( q ) );
b := R!Rq!( (b * (2 - a * b)) mod (X^N - 1) );
end while;
return b;
end function;
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: Tying Up Loose Ends - Correction
Date: 26 Sep 2000 05:34:52 GMT
Mok-Kong Shen wrote:
>
>
>BTW, could you answer my question of whether Scott's
>1-1 scheme can deal with arbitrary boundaries, since
>you are apparently fairly familiar with that? (I
>failed to obtain that information from him directly.)
>
There is a standard Usenet technique for finding things out.
Let's say that you are on a Brady Bunch newsgroup an want to
know what happened to the youngest Brady girl. Just asking
"what happened to the youngest Brady girl?" will be ignored.
Instead, write "I know for a fact that the youngest Brady
girl served in Vietnam as a nurse then later became a porn
star." *That* will get you replies! Just tell Scott that
it's too bad that his 1-1 scheme can't deal with arbitrary
boundaries and see what he says. Then tell him to read your
web page for reasons why he is wrong. ;)
------------------------------
From: "kihdip" <[EMAIL PROTECTED]>
Subject: Re: Encryption Project
Date: Tue, 26 Sep 2000 08:17:26 +0200
<snip>
>and using 40 bit encryption (I have to use that because I'm in the UK don't
>I?),
<snip>
40 bit encryption ?? - As long as you're not trying to protect anyones
payroll it'll be fine... ;-)
USA has eased the distinction between weak and strong cryptography and
allows export of strong (>40 bits) cryptography to all members of EU, five
European countries outside the EU along with Japan, Australia and New
Zealand.
Kim
------------------------------
From: "kihdip" <[EMAIL PROTECTED]>
Subject: Test for weak keys in 3DES
Date: Tue, 26 Sep 2000 08:33:01 +0200
In RFC2409 it is stated that you should test your key before use in a DES
CBC encryption, and be sure it is not a weak or semi-weak key.
This is not mentioned for 3DES CBC encryption. Does it matter whether you
use weak keys in 3DES ??
Kim
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: On block encrpytion processing with intermediate permutations
Date: Tue, 26 Sep 2000 07:00:19 GMT
Mok-Kong Shen wrote:
>
> I should very much appreciate comments on the following idea:
>
> Given a common block cipher of m cycles (for a Feistel
> cipher, a cycle means 2 rounds, i.e. processing steps
> resulting in all bits of the block being processed once),
> we can, in case of software implementation, does processing
> of one cycle for all blocks of the message, then perform
> a pseudo-random permutation of the words of the entire
> message, thus rearranging the contents of each individual
> block, before doing processing of the next following cycle
> (again for all blocks of the message), and so on till all
> m cycles are done.
Tom is right; the diffusion is obviously terrible.
Here's a first-cut at an attack strategy:
In a typical Fiestel cipher one might have 16 rounds
or 8 round-pairs. Let's use chosen messages of about a
thousand blocks. We introduce differential pairs in
which only one block input differs. There probably
exists a left half-block for which any input
differential survives to become an output differential.
That happens if at each of the seven between-round
permutations the differential goes into a left block
and the right blocks are still constant.
We can easilly detect the case when it happens; the
differential put into the left half of input block
'i', appears as the differential comming out of the
left half of ouput block 'j'. Now we can put
differntial pairs into the right half of i, holding
everything else constant, and the differential that
comes out in the left half of j is exactly the
differential from the right half of i going through
the f function in the first round. For most Feistel
ciphers that will expose the first round-key, and
allow us to push to the next round.
There are other opportunities to extract information
based on the poor diffusion. As a rule of thumb,
letting information out from intermediate rounds is
extremely dangerous.
--Bryan
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
** 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
******************************
