Cryptography-Digest Digest #718, Volume #11 Sat, 6 May 00 15:13:01 EDT
Contents:
Re: SBOX program using ideas from CA and ST (CAST design) (Tim Tyler)
Re: Crypto Export ("Adam Durana")
Re: Fresco transmits my name (was: Spammed after just visiting a site) ("David J.
Ruck")
Is this random? (Benjamin Goldberg)
Re: SBOX program using ideas from CA and ST (CAST design) (Tom St Denis)
Re: Questions about imaginary quadratic orders (Jan-Christoph Puchta)
Re: Newbie question about generating primes ("JoeC")
Re: Increasing bit Entropy (Guy Macon)
----------------------------------------------------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: SBOX program using ideas from CA and ST (CAST design)
Reply-To: [EMAIL PROTECTED]
Date: Sat, 6 May 2000 17:43:34 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
: Tim Tyler wrote:
:> Tom St Denis <[EMAIL PROTECTED]> wrote:
:> : Tim Tyler wrote:
:> :> Tom St Denis <[EMAIL PROTECTED]> wrote:
:> :> I know of no way of calculating the maximum non-linearity of a
:> :> variable-size boolean function (and would be interested to learn of
:> :> any that accurately determine it and are much faster than testing all
:> :> functions of that size).
:> :>
:> :> The maximum non-linearity values for small values of n are known, though.
:>
:> : I read up that a function is perfectly non-linear (i.e bent) if
:>
:> : |FW(f)w| = 2^(n-2) for all w
:>
:> : Where FW is the walsh transform of the GF(2)^n -> GF(2) function 'f'
:> : and 'n' is the number of bits in the input, 0 <= w < 2^n. [...]
:>
:> If I'm following your notation correctly, a function is bent iff
:> |FW(f)w| = k for all w, and some k.
:>
:> I don't see why k should be equal to 2^(n-2) - and indeed according to my
:> sums, for n = 4, k doesn't equal this value.
: The best you can do for a 4x1 function is -4/4 or '4'. 2^(4-2) = 4, so
: the statement is valid for 4 bit input functions.
Not so. I suspect you won't be able to exhibit a function with all
entires in the WT being +-4.
Here is a table whose WT produces entries that are all +-2:
{0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0}
:> : Then you can't have perfectly non-linear functions when 'n' is odd?
:>
:> I don't see why that would follow from the above equation.
: I think I read that... I might be mistaken...
It might well be right - I just didn't see why it followed.
A cursory look on my part didn't succeed in locating any such
functions.
[WT on 4x1 boolean function]
:> 4 /might/ be the best you can do if there are some constraints on the
:> function. If, say the function must have equal numbers of 0s and 1s in
:> the output table, a bound of +-4 would be the best you could get.
: Yeah of course I am talking of 0/1 balanced, the goal is to form a
: bijection.
Ah. I might have been put off the scent by your mentioning that the
function was bent. No bent function can possibly fit this description.
:> : How does this notation of bent extend to n by n functions?
:>
:> My preferred method would be to treat this as a series of nx1 functions,
:> calculate the non-linearity, and then take the /minimum/ of these values
:> as a value representing the non-linearity of the whole table.
:>
:> But this is just my view - there are other ways you could get a
:> non-linearity value for an nxn function.
: Well for nxn functions you have to use the FW over all possible input
: masks and output masks to find the "most linear" correlation between
: input and output bits.
I'm not sure what you're getting at here. I'd still be inclined to do
one WT per output bit. If you think there's a preferrable method of
getting the non-linearity of a nxn function than the one I mentioned,
I'd be happy to learn what it is.
: I wonder which method is better, make eight 8x1 functions tack them
: together to test, or make random 8x8 functions and test ...
FWIW, I've always made permutations first, and then tested the results
for non-linearity - but I've not had cause to construct very large
tables, or to worry overly much about the speed.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Be good, do good.
------------------------------
From: "Adam Durana" <[EMAIL PROTECTED]>
Subject: Re: Crypto Export
Date: Sat, 6 May 2000 14:15:43 -0400
> > Actually there is a sensible argument and you have most likely heard it,
but
> > you didn't like it. As long as the US puts limits on the export of
> > technologies that use strong cryptographic algorithms there is no way
some
> > sort of basic communications standard will evolve that incorporates
strong
> > crypto. Sure you might say there are already many standards that
involve
> > strong crypto, but there is still a great deal of communications that go
on
> > around the world that don't use strong crypto or any encryption at all.
> > From the standpoint of the agencies, such as the NSA and CIA, that
monitor
> > communications around the world, this situation is ideal. Now if there
was
> > no limits on the export of crypto, eventually every method of
communication
> > would be encrypted in some form. And this would make those agencies'
job's
> > a lot harder.
> >
> > I'm sure you've heard this claim before, and it does make sense. I am
not
> > saying its good or bad, but it does make sense.
> >
> > - Adam
>
> No. It only means that American citizens will not develop and deploy those
> technologies. It makes no sense for a government to harm its own people.
Stop and think about it for a minute. The United States is one of the top
economic powers in the world. A lot of businesses are based in the United
States, and a good deal of these businesses are leaders in their fields.
Now for a standard to evolve, people have to agree. If a proposal for some
sort of standard was to come along, that included something American
businesses were not going to be able to export or have a very hard time
exporting from the US, none of these American business affected by the
standard would agree to it. So as long as there is some sort of limit on
the export of crypto from the US, and the US remains an economic power, it
will be very difficult for crypto to work its way into all forms of
communications. If you can't see this, then you aren't looking at the whole
picture.
- Adam
------------------------------
Crossposted-To: comp.sys.acorn.misc
From: "David J. Ruck" <[EMAIL PROTECTED]>
Subject: Re: Fresco transmits my name (was: Spammed after just visiting a site)
Date: Sat, 6 May 2000 17:23:16 +0100
In article <[EMAIL PROTECTED]>, Mark Wooding
<URL:mailto:[EMAIL PROTECTED]> wrote:
> * The US government have persuaded all vendors of SSL3 software to
^
US
> insert a back door for them in their implementations, although
> nobody has noticed it. This includes the developers of OpenSSL,
> who are based outside the United States and whose software is
^^^^^^^
> released in source form and widely reviewed by experienced security
> experts and cryptographers.
For further research look into certificate issuing authorities, i.e. Verisign
and their relationship to certain branches of the US government.
(Que greg's denials, backed up his hard evidence of using swear words :-)
---druck
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Is this random?
Date: Sat, 06 May 2000 18:33:21 GMT
I've come across a number generator written in java which claims to be
"truly random" number generator (not a PRNG)... Could someone tell me
how accurate (or inaccurate) this claim is?
public class ThreadYieldGenerator
extends java.util.Random
implements Runnable {
public static final java.util.Random TYG =
new ThreadYieldGenerator();
private Thread generator;
private long time = 1000;
private int count;
private ThreadYieldGenerator() {
generator = new Thread(this,"TYG-generator");
generator.setDaemon(true);
generator.start();
}
public synchronized byte getByte() {
try {
generator.join();
} catch(InterruptedException ie) {
generator.stop();
}
int count = this.count;
generator = new Thread(this,"TYG-generator");
generator.setDaemon(true);
generator.start();
return (byte)count;
}
public void run() {
if( Thread.currentThread() != generator ) {
try {
Thread.sleep(time);
} catch(InterruptedException ie) {
}
return;
}
do {
count = 0;
Thread sleeper = new Thread(this,"TYG-sleeper");
sleeper.setDaemon(true);
sleeper.start();
while( sleeper.isAlive() ) {
Thread.yield();
++count;
}
time = ( time * 55000 / count ) | 1;
} while( count < 33000 );
}
private long bitsValue = 0;
private int bitsCount = 0;
public int getInt(int nbits) {
if( nbits > 32 || nbits < 0 )
return 0;
while( bitsCount < nbits ) {
bitsCount += 8;
bitsValue = (bitsValue<<8) | (getByte()&0xFF);
}
bitsCount -= nbits;
return (int)
( bitsValue >>> bitsCount ) &
( (1<<nbits) - 1 );
}
}
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: SBOX program using ideas from CA and ST (CAST design)
Date: Sat, 06 May 2000 18:39:14 GMT
Tim Tyler wrote:
>
> Tom St Denis <[EMAIL PROTECTED]> wrote:
> : Tim Tyler wrote:
> :> Tom St Denis <[EMAIL PROTECTED]> wrote:
> :> : Tim Tyler wrote:
> :> :> Tom St Denis <[EMAIL PROTECTED]> wrote:
>
> :> :> I know of no way of calculating the maximum non-linearity of a
> :> :> variable-size boolean function (and would be interested to learn of
> :> :> any that accurately determine it and are much faster than testing all
> :> :> functions of that size).
> :> :>
> :> :> The maximum non-linearity values for small values of n are known, though.
> :>
> :> : I read up that a function is perfectly non-linear (i.e bent) if
> :>
> :> : |FW(f)w| = 2^(n-2) for all w
> :>
> :> : Where FW is the walsh transform of the GF(2)^n -> GF(2) function 'f'
> :> : and 'n' is the number of bits in the input, 0 <= w < 2^n. [...]
> :>
> :> If I'm following your notation correctly, a function is bent iff
> :> |FW(f)w| = k for all w, and some k.
> :>
> :> I don't see why k should be equal to 2^(n-2) - and indeed according to my
> :> sums, for n = 4, k doesn't equal this value.
>
> : The best you can do for a 4x1 function is -4/4 or '4'. 2^(4-2) = 4, so
> : the statement is valid for 4 bit input functions.
>
> Not so. I suspect you won't be able to exhibit a function with all
> entires in the WT being +-4.
>
> Here is a table whose WT produces entries that are all +-2:
>
> {0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0}
Which is not 0/1 balanced, thus not a bijection.
> :> : Then you can't have perfectly non-linear functions when 'n' is odd?
> :>
> :> I don't see why that would follow from the above equation.
>
> : I think I read that... I might be mistaken...
>
> It might well be right - I just didn't see why it followed.
> A cursory look on my part didn't succeed in locating any such
> functions.
>
> [WT on 4x1 boolean function]
>
> :> 4 /might/ be the best you can do if there are some constraints on the
> :> function. If, say the function must have equal numbers of 0s and 1s in
> :> the output table, a bound of +-4 would be the best you could get.
>
> : Yeah of course I am talking of 0/1 balanced, the goal is to form a
> : bijection.
>
> Ah. I might have been put off the scent by your mentioning that the
> function was bent. No bent function can possibly fit this description.
I may have been confused, what does bent mean exactly?
>
> :> : How does this notation of bent extend to n by n functions?
> :>
> :> My preferred method would be to treat this as a series of nx1 functions,
> :> calculate the non-linearity, and then take the /minimum/ of these values
> :> as a value representing the non-linearity of the whole table.
> :>
> :> But this is just my view - there are other ways you could get a
> :> non-linearity value for an nxn function.
>
> : Well for nxn functions you have to use the FW over all possible input
> : masks and output masks to find the "most linear" correlation between
> : input and output bits.
>
> I'm not sure what you're getting at here. I'd still be inclined to do
> one WT per output bit. If you think there's a preferrable method of
> getting the non-linearity of a nxn function than the one I mentioned,
> I'd be happy to learn what it is.
You have to consider all the output bits though, and by checking all
inputs and outputs you in fact test all one bit expressions too.
> : I wonder which method is better, make eight 8x1 functions tack them
> : together to test, or make random 8x8 functions and test ...
>
> FWIW, I've always made permutations first, and then tested the results
> for non-linearity - but I've not had cause to construct very large
> tables, or to worry overly much about the speed.
How big are the permutations?
In my sboxgen.c (http://www.tomstdenis.com/sboxgen.c) I use a bunch of
tables to speed up the WT code.
Tom
------------------------------
From: Jan-Christoph Puchta <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Questions about imaginary quadratic orders
Date: Sat, 06 May 2000 20:06:16 +0200
David Hopwood wrote:
> Let Delta be a negative integer such that abs(Delta) is prime, and
> Delta is congruent to 1 (mod 4),
> q be a prime integer,
> Delta_q = Delta.q^2,
> Cl(Delta) be the class group of the maximal imaginary quadratic order
> with discriminant Delta,
> Cl(Delta_q) be the class group of the non-maximal imaginary quadratic
> order with discriminant Delta_q.
>
> 1. Am I correct in thinking that the class number, h(Delta), is just the
> order of the class group, |Cl(Delta)| (and similarly for h(Delta_q))?
yes.
>
> 2. What is the expected size or range of |Cl(Delta)|, and does its
> factorisation "look like" the factorisation of a random integer of
> about the same size?
AFAIK the best effective bounds are C_1 (log log Delta)^(1/2) < h(Delta)
< C_2 Delta^(1/2) log Delta. However, if GRH holds, we have
C_1 Delta^(1/2) (log log Delta)^(-1) < h(Delta) < C_2 Delta^(1/2) (log
log Delta), and this is sharp. Further, you can replace GRH with some
finite statement like "L(s, \chi) has no zero in the domain Re s> 6/7,
Im s < log^3 Delta", then using density estimates one gets that the
estimate for h(Delta) holds for almost all Delta unconditionally (but
with weaker constants).
The factors of h(Delta) are not completely random, the Gauss' theory of
genus describes its 2-part, and you can construct Delta such that
h(Delta) is divisible by some prescribed prime. E.G. if the equation
x^2+Delta = y^k is solvable, in most cases (there are some trivial
solutions) we have k|h(Delta).
> 5. In Cl(D) and in Z*_n (the group of units modulo a composite integer
> n), taking discrete logarithms requires factoring a parameter that
> describes the group (D or n), then calculating discrete logarithms
> in a smaller group or groups dependent on the factorisation.
>
> Are there any other finite groups that share this property?
What about abstract cyclic groups? Assume you have an algorithm to
compute the product of two elements and to check equality of elements,
and that a generator a of G is given. Factor |G|. Choose some k| |G|
with (k, |G|)=1. Then we have G = U x V for subgroups U, V with |U|=k,
|V|=|G|/k. We can choose U=<a^(|G|/k)>, V=<a^k>. Assume that we can
solve discrete logarithms in U and V. Let x in G be given, and we want
to compute some l such that a^l=x in G. Compute x^(|G|/k). This is in U,
solving discrete logarithms in U gives some n such that a^(n |G|/k) =
x^(|G|/k), in V we find some n' such that a^(n' k) = x^k. Find integers
u, v, such that u(|G|/k) + v k = 1, and we obtain a^(u n |G|/k + v n'
k) = x, hence we found our logarithm.
Jan-Christoph Puchta
------------------------------
From: "JoeC" <[EMAIL PROTECTED]>
Crossposted-To: alt.math
Subject: Re: Newbie question about generating primes
Date: Sat, 6 May 2000 19:49:54 +0100
Dann Corbit <[EMAIL PROTECTED]> wrote in message
news:gAPQ4.1790$dv6.2760@client...
> "JoeC" <[EMAIL PROTECTED]> wrote in message
> news:8f0bbe$28t$[EMAIL PROTECTED]...
> > As I understand it, one of the key factors(pardon the pun) in the
security
> > of PGP and similar is the time taken to factor a large prime number.
> > Does it not take an equally large amount of time to create a prime,
which
> I
> > would need were I to create a private/public key pair?
>
> Creating a prime is trivial compared to factoring a number of the same
size.
> Once you have coughed up a candidate of about the right size, Miller's
test
> can be "really darn sure" that it is prime and if you are paranoid, you
can
> use APR-CL or ECPP to prove it. This is still pretty fast. And the
product
> of two large primes will be a much larger object which will be very tough
to
> factor indeed.
>
> > [ Obviously it can't, or it wouldn't work. ]
> > Could someone point me at a good source (or is there a quick
explanation)
> > for the obvious time difference between creating a prime, compared to
> > factoring one, since I thought in order to determine if a number was
> prime,
> > you had to factor it?
>
> You can't factor a prime (other than the trivial factorization (p,1)).
Iin my own defence I did know that, but I didnt realise there were other
ways to discover if a number was prime rather than just attempting to factor
it.
> Take a look here:
> http://www.utm.edu/research/primes/
>
Thanks,
Joe
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: Increasing bit Entropy
Date: 06 May 2000 14:53:55 EDT
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Tim Tyler) wrote:
>
>RavingCow <[EMAIL PROTECTED]> wrote:
>
>: If I have two streams of bits with a entropy of 0.5 bits / bit, how can
>: I combine these to increase randomness? Obviously, XOR would not be a
>: good choice, but would addition mod. 2 work? Would the entropy go up to
>: 0.75, or would it be less?
>
>From: Tim Tyler <[EMAIL PROTECTED]>
>Subject: Re: Increasing bit Entropy
>Newsgroups: sci.crypt
>References: <[EMAIL PROTECTED]>
>Organization:
>Reply-To: [EMAIL PROTECTED]
>
>RavingCow <[EMAIL PROTECTED]> wrote:
>
>: If I have two streams of bits with a entropy of 0.5 bits / bit, how can
>: I combine these to increase randomness?
>
>Feed them into a hash.
>
>: Obviously, XOR would not be a good choice, but would addition mod. 2 work?
>
>Addition mod. 2 *is* XOR ;-)
>
>: Would the entropy go up to 0.75, or would it be less?
>
>With XOR 0.75 sounds like a very reasonable figure - if the streams are
>independent.
>
>With a hash you should be able to do *much* better...
Could someone explain (or point to a site that explains) in very simple
clueless newbie friendly terms how to take a stream that is a combination
of true random and nonrandom bits and turn it into a shorter stream with
a higher percentage of true random bits? I have been looking at lavarand,
which clearly has (at the digitized image leval) some bits which are random
and a lot which are not.
------------------------------
** 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
******************************
