Cryptography-Digest Digest #27, Volume #12 Wed, 14 Jun 00 16:13:00 EDT
Contents:
New Idea (csybrandy)
Re: Threshold Schemes. (James Pate Williams, Jr.)
Re: Threshold Schemes. (James Pate Williams, Jr.)
Re: New Idea (tomstd)
Re: Threshold Schemes. (James Pate Williams, Jr.)
Re: Why the golden ratio? (Tim Tyler)
Re: Random sboxes... real info (Tim Tyler)
Re: New Idea (tomstd)
Re: Finding prime numbers (Anton Stiglic)
Re: Cryptanalytic gap [was: Re: Some dumb questions] ("John E. Kuslich")
Re: Digits of pi in Twofish ([EMAIL PROTECTED])
Re: Card Shuffling Protocol (zapzing)
----------------------------------------------------------------------------
From: csybrandy <[EMAIL PROTECTED]>
Subject: New Idea
Date: Wed, 14 Jun 2000 14:53:34 -0400
Reply-To: [EMAIL PROTECTED]
I retract (hehe) what I said before about retireing from the cipher
design arena. It seems you can blame Tom for this since I got this idea
from reading his paper (which isn't too bad so far)
What gave me this idea was when he stated that data dependent rotates
(so far) never use all of the bits in a word. That got me thinking, how
would I solve this problem? The first idea I had, assuming 32-bit
words, was to extract 6-5 bit values from a single word. This left us
with 2 bits unused, so I figured I could do better. Next I thought
about 8-4 bit values, but I figured that would be too many try to use
and would create a very slow s-box (unless you have hardware rotates).
What I finally came up with was creating 4 values by adding pairs of 4
bit values from the total of 8. Here's an example:
& = bitwise AND
>> = right shift
a1 = (A & 15) + ((A >> 4) & 15)
a2 = ((A >> 8) & 15) + ((A >> 12) & 15)
a3 = ((A >> 16) & 15) + ((A >> 20) & 15)
a4 = ((A >> 24) & 15) + ((A >> 28) & 15)
Now if you add the next equation consisting of right rotates (>>>), left
rotates (<<<), additions, and exclusive or's (^), you have a simple
f-function:
B = B + (A >>> a1) ^ (A <<< a2) + (A >>> a3) ^ (A <<< a4) + k[i]
I don't know how good this f-function is, it is merely an example of how
to use all of the bits. Currently the values a1..a4 can only be values
from 0-30, but you can easily change that by adding 1, which changes the
range to 1..31.
Well, it's an idea. What does everyone think? If you swap the A's and
B's on the right hand side of the last equation, it could turn into a
nice hash function.
csybrandy
------------------------------
From: [EMAIL PROTECTED] (James Pate Williams, Jr.)
Subject: Re: Threshold Schemes.
Date: Wed, 14 Jun 2000 19:26:39 GMT
On Wed, 14 Jun 2000 18:19:14 GMT, Simon Johnson
<[EMAIL PROTECTED]> wrote:
>Now, that i'm more awake, i'll make another attempt at this post :p.
>
>Basically this concerns the Threshold Scheme on Pg. 528-529 of Applied
>Cryptography. In Schneier's example he uses the shadows:
>
>3 mod 13, 7 mod 13 and 5 mod 13.
>
>To reconstruct the message, solve this set of linear equations:
>
>a(2^2) + (2*b) + m = 3 mod 13
>a(3^2) + (3*b) + m = 7 mod 13
>a(5^2) + (5*b) + m = 5 mod 13
>
>I'm looking for a sure-fire way to find these coeffients. I can solve
>it, but i need to know how many times the shadow was reduced during
>computation.
>
>Anyone willing to help?, please complete the example to show working.
>--
>Hi, i'm the signuture virus,
>help me spread by copying me into Signiture File
>
>--
>Hi, i'm the signuture virus,
>help me spread by copying me into Signiture File
>
>
>Sent via Deja.com http://www.deja.com/
>Before you buy.
/*
Author: Pate Williams (c) 1997
Shamir secret sharing. See "Applied Cryptography"
by Bruce Schneier second edition 23.2 Section
pages 528 - 529. Also see "A Course in
Computational Algebraic Number Theory" by Henri
Cohen Algorithm 2.2.1 pages 48 - 49.
*/
#include <assert.h>
#include <malloc.h>
#include <stdio.h>
long **create_square_matrix(long n)
{
long i, **matrix = calloc(n, sizeof(long *));
assert(matrix != 0);
for (i = 0; i < n; i++) {
matrix[i] = calloc(n, sizeof(long));
assert(matrix[i] != 0);
}
return matrix;
}
void delete_matrix(long n, long **matrix)
{
long i;
for (i = 0; i < n; i++) free(matrix[i]);
free(matrix);
}
void extended_euclid(long a, long b, long *x, long *y, long *d)
{
long q, r, x1, x2, y1, y2;
if (b == 0) {
*d = a, *x = 1, *y = 0;
return;
}
x2 = 1, x1 = 0, y2 = 0, y1 = 1;
while (b > 0) {
q = a / b, r = a - q * b;
*x = x2 - q * x1, *y = y2 - q * y1;
a = b, b = r;
x2 = x1, x1 = *x;
y2 = y1, y1 = *y;
}
*d = a, *x = x2, *y = y2;
}
long inv(long number, long modulus)
{
long d, x, y;
extended_euclid(number, modulus, &x, &y, &d);
assert(d == 1);
if (x < 0) x += modulus;
return x;
}
void gaussian_elimination(long n, long p, long *b, long *x, long **m)
{
int found;
long ck, d, i, j, k, l, sum, t;
for (j = 0; j < n - 1; j++) {
found = 0, i = j;
while (!found && i < n) {
found = m[i][j] != 0;
if (!found) i++;
}
assert(found != 0);
if (i > j) {
/* exchange colums */
for (l = j; l < n; l++) {
t = m[i][l], m[i][l] = m[j][l], m[j][l] = t;
t = b[i], b[i] = b[j], b[j] = t;
}
}
d = inv(m[j][j], p);
for (k = j + 1; k < n; k++) {
ck = (d * m[k][j]) % p;
if (ck < 0) ck += p;
for (l = j + 1; l < n; l++) {
m[k][l] -= ck * m[j][l];
m[k][l] %= p;
if (m[k][l] < 0) m[k][l] += p;
}
b[k] -= ck * b[j];
b[k] %= p;
if (b[k] < 0) b[k] += p;
}
}
for (i = n - 1; i >= 0; i--) {
sum = 0;
for (j = i + 1; j < n; j++)
sum += m[i][j] * x[j];
x[i] = (inv(m[i][i], p) * (b[i] - sum)) % p;
if (x[i] < 0) x[i] += p;
}
}
long F(long a, long b, long M, long x, long p)
{
return (a * x * x + b * x + M) % p;
}
int main(void)
{
long b[3], i, **m = create_square_matrix(3), n = 3;
long p = 13, x[3];
m[0][0] = 4, m[0][1] = 2, m[0][2] = 1;
m[1][0] = 9, m[1][1] = 3, m[1][2] = 1;
m[2][0] = 25, m[2][1] = 5, m[2][2] = 1;
b[0] = F(7, 8, 11, 2, p);
b[1] = F(7, 8, 11, 3, p);
b[2] = F(7, 8, 11, 5, p);
printf("the right hand side is as follows:\n\n");
for (i = 0; i < n; i++)
printf("%ld\n", b[i]);
gaussian_elimination(n, p, b, x, m);
printf("\nthe solution vector is as follows:\n\n");
for (i = 0; i < n; i++)
printf("%ld\n", x[i]);
delete_matrix(n, m);
return 0;
}
==Pate Williams==
[EMAIL PROTECTED]
http://www.mindspring.com/~pate
------------------------------
From: [EMAIL PROTECTED] (James Pate Williams, Jr.)
Subject: Re: Threshold Schemes.
Date: Wed, 14 Jun 2000 19:28:47 GMT
On Wed, 14 Jun 2000 18:19:14 GMT, Simon Johnson
<[EMAIL PROTECTED]> wrote:
>Now, that i'm more awake, i'll make another attempt at this post :p.
>
>Basically this concerns the Threshold Scheme on Pg. 528-529 of Applied
>Cryptography. In Schneier's example he uses the shadows:
>
>3 mod 13, 7 mod 13 and 5 mod 13.
>
>To reconstruct the message, solve this set of linear equations:
>
>a(2^2) + (2*b) + m = 3 mod 13
>a(3^2) + (3*b) + m = 7 mod 13
>a(5^2) + (5*b) + m = 5 mod 13
>
>I'm looking for a sure-fire way to find these coeffients. I can solve
>it, but i need to know how many times the shadow was reduced during
>computation.
>
>Anyone willing to help?, please complete the example to show working.
>--
>Hi, i'm the signuture virus,
>help me spread by copying me into Signiture File
>
>--
>Hi, i'm the signuture virus,
>help me spread by copying me into Signiture File
>
>
>Sent via Deja.com http://www.deja.com/
>Before you buy.
/*
Author: Pate Williams (c) 1997
Shamir's (t, n) threshold secret sharing scheme.
Second program. Uses a modification of the output
of secret as input. The input in stdin should be
as follows:
n
t
prime_number
secret_number
sequence_number_1 shadow_1
...
sequence_number_t shadow_t
where 1 <= sequence_number_i <= t.
*/
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include "lip.h"
verylong **create_square_matrix(long n)
{
long i;
verylong **zmatrix = calloc(n, sizeof(verylong *));
assert(zmatrix != 0);
for (i = 0; i < n; i++) {
zmatrix[i] = calloc(n, sizeof(verylong));
assert(zmatrix[i] != 0);
}
return zmatrix;
}
void delete_matrix(long n, verylong **zmatrix)
{
long i, j;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++)
zfree(&zmatrix[i][j]);
free(zmatrix[i]);
}
free(zmatrix);
}
void gaussian_elimination(long n, verylong zp, verylong *zb,
verylong *zx, verylong **zm)
{
int found;
long i, j, k, l;
verylong zck = 0, zd = 0, zs = 0, zsum = 0, zt = 0;
for (j = 0; j < n - 1; j++) {
found = 0, i = j;
while (!found && i < n) {
found = zscompare(zm[i][j], 0l) != 0;
if (!found) i++;
}
assert(found != 0);
if (i > j) {
/* exchange colums */
for (l = j; l < n; l++) {
zcopy(zm[i][l], &zt);
zcopy(zm[j][l], &zm[i][l]);
zcopy(zt, &zm[j][l]);
zcopy(zb[i], &zt);
zcopy(zb[j], &zb[i]);
zcopy(zt, &zb[j]);
}
}
zinvmod(zm[j][j], zp, &zd);
for (k = j + 1; k < n; k++) {
zmulmod(zd, zm[k][j], zp, &zck);
for (l = j + 1; l < n; l++) {
zmul(zck, zm[j][l], &zt);
zsubmod(zm[k][l], zt, zp, &zsum);
zcopy(zsum, &zm[k][l]);
}
zmul(zck, zb[j], &zt);
zsubmod(zb[k], zt, zp, &zsum);
zcopy(zsum, &zb[k]);
}
}
for (i = n - 1; i >= 0; i--) {
zzero(&zsum);
for (j = i + 1; j < n; j++) {
zmul(zm[i][j], zx[j], &zt);
zadd(zt, zsum, &zs);
zcopy(zs, &zsum);
}
zinvmod(zm[i][i], zp, &zd);
zsub(zb[i], zsum, &zt);
zmulmod(zd, zt, zp, &zx[i]);
}
zfree(&zck);
zfree(&zd);
zfree(&zs);
zfree(&zsum);
zfree(&zt);
}
int main(void)
{
long i, j, n, t, x;
verylong za = 0, zp = 0, zs = 0, *zb, *zx, **zm;
fscanf(stdin, "%ld", &n);
fscanf(stdin, "%ld", &t);
zb = calloc(t, sizeof(verylong));
assert(zb != 0);
zx = calloc(t, sizeof(verylong));
assert(zx != 0);
zm = create_square_matrix(t);
zread(&zp);
zwriteln(zp);
zread(&zs);
zwriteln(zs);
for (i = 0; i < t; i++) {
fscanf(stdin, "%ld", &x);
zintoz(x, &za);
zread(&zb[i]);
for (j = 0; j < t; j++)
zsexp(za, j, &zm[i][j]);
printf("%ld ", x);
zwriteln(zb[i]);
}
gaussian_elimination(t, zp, zb, zx, zm);
zwriteln(zx[0]);
if (zcompare(zs, zx[0]) == 0)
printf("secret verified\n");
else
printf("secret not verified\n");
for (i = 0; i < t; i++) {
zfree(&zb[i]);
zfree(&zx[i]);
}
delete_matrix(t, zm);
free(zb);
free(zx);
zfree(&za);
zfree(&zp);
zfree(&zs);
return 0;
}
==Pate Williams==
[EMAIL PROTECTED]
http://www.mindspring.com/~pate
------------------------------
Subject: Re: New Idea
From: tomstd <[EMAIL PROTECTED]>
Date: Wed, 14 Jun 2000 12:16:18 -0700
In article <[EMAIL PROTECTED]>, csybrandy
<[EMAIL PROTECTED]> wrote:
>I retract (hehe) what I said before about retireing from the
cipher
>design arena. It seems you can blame Tom for this since I got
this idea
>from reading his paper (which isn't too bad so far)
Hehehe, thanks. I can't wait till after exams so I can
concentrate on it. My pile-o-papers is getting bigger so I will
be able to do a lot deeper survey on block ciphers.
>What gave me this idea was when he stated that data dependent
rotates
>(so far) never use all of the bits in a word. That got me
thinking, how
>would I solve this problem? The first idea I had, assuming 32-
bit
>words, was to extract 6-5 bit values from a single word. This
left us
>with 2 bits unused, so I figured I could do better. Next I
thought
>about 8-4 bit values, but I figured that would be too many try
to use
>and would create a very slow s-box (unless you have hardware
rotates).
>What I finally came up with was creating 4 values by adding
pairs of 4
>bit values from the total of 8. Here's an example:
>
>& = bitwise AND
>>> = right shift
>
>a1 = (A & 15) + ((A >> 4) & 15)
>a2 = ((A >> 8) & 15) + ((A >> 12) & 15)
>a3 = ((A >> 16) & 15) + ((A >> 20) & 15)
>a4 = ((A >> 24) & 15) + ((A >> 28) & 15)
>
>Now if you add the next equation consisting of right rotates
(>>>), left
>rotates (<<<), additions, and exclusive or's (^), you have a
simple
>f-function:
>
>B = B + (A >>> a1) ^ (A <<< a2) + (A >>> a3) ^ (A <<< a4) + k[i]
>
>I don't know how good this f-function is, it is merely an
example of how
>to use all of the bits. Currently the values a1..a4 can only
be values
>from 0-30, but you can easily change that by adding 1, which
changes the
>range to 1..31.
>
>Well, it's an idea. What does everyone think? If you swap the
A's and
>B's on the right hand side of the last equation, it could turn
into a
>nice hash function.
Just off the top off my head I would say finding collisions in
the rotates would be the way to go. For example with:
>a1 = (A & 15) + ((A >> 4) & 15)
You try to make two different A values, let's say A and A' that
make the same a1' value. Which isn't that hard.
Also if you are rotating 32 bits with a1 as in
>B = B + (A >>> a1) ^ (A <<< a2) + (A >>> a3) ^ (A <<< a4) + k[i]
Then you are in for a shock by noting that rotates >16 are not
as probable as <16.
So basically you find collisions in a1 thru a4 (or any tuple of
them) that is under 16 (which is more probable) and voila you
get very bad chi-square stats.
Tada... are you angry now? Hehehehe... This is all off the top
of my head, so I could be wrong
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: [EMAIL PROTECTED] (James Pate Williams, Jr.)
Subject: Re: Threshold Schemes.
Date: Wed, 14 Jun 2000 19:31:10 GMT
On Wed, 14 Jun 2000 18:19:14 GMT, Simon Johnson
<[EMAIL PROTECTED]> wrote:
>Now, that i'm more awake, i'll make another attempt at this post :p.
>
>Basically this concerns the Threshold Scheme on Pg. 528-529 of Applied
>Cryptography. In Schneier's example he uses the shadows:
>
>3 mod 13, 7 mod 13 and 5 mod 13.
>
>To reconstruct the message, solve this set of linear equations:
>
>a(2^2) + (2*b) + m = 3 mod 13
>a(3^2) + (3*b) + m = 7 mod 13
>a(5^2) + (5*b) + m = 5 mod 13
>
>I'm looking for a sure-fire way to find these coeffients. I can solve
>it, but i need to know how many times the shadow was reduced during
>computation.
>
>Anyone willing to help?, please complete the example to show working.
>--
>Hi, i'm the signuture virus,
>help me spread by copying me into Signiture File
>
>--
>Hi, i'm the signuture virus,
>help me spread by copying me into Signiture File
>
>
>Sent via Deja.com http://www.deja.com/
>Before you buy.
/*
Author: Pate Williams (c) 1997
Shamir's (t, n) threshold secret sharing scheme
generation program. The command line is as follows:
secret length t n
where length, t, n, and are long integers. See
"Handbook of Applied Cryptography" by Alfred J.
Menezes et al 12.7.2 Section pages 525-526.
*/
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "lip.h"
long OddRandom(long bit_length)
{
long i, mask = 1, n;
bit_length--;
for (i = 1; i <= bit_length; i++)
mask |= 1 << i;
if (bit_length < 16)
n = (1 << bit_length) | rand();
else
n = (1 << bit_length) | (rand() << 16) | rand();
n &= mask;
if ((n & 1) == 0) n++;
return n;
}
void PROVABLE_PRIME(long k, verylong *zn)
{
double c, r, s;
int success;
long B, m, n, p, sqrtn;
verylong zI = 0, zR = 0, za = 0, zb = 0, zc = 0;
verylong zd = 0, zk = 0, zl = 0, zq = 0, zu = 0;
srand(time(NULL));
if (k <= 20) {
do {
n = OddRandom(k);
sqrtn = sqrt(n);
zpstart2();
do p = zpnext(); while (n % p != 0 && p < sqrtn);
} while (p < sqrtn);
zintoz(n, zn);
}
else {
c = 0.1;
m = 20;
B = c * k * k;
if (k > 2 * m)
do {
s = rand() / (double) RAND_MAX;
r = pow(2.0, s - 1.0);
} while (k - r * k <= m);
else
r = 0.5;
PROVABLE_PRIME(r * k + 1, &zq);
zrstarts(time(NULL));
zone(&za);
zlshift(za, k - 1, &zk);
zcopy(zq, &za);
zlshift(za, 1l, &zl);
zdiv(zk, zl, &zI, &za);
zsadd(zI, 1l, &zl);
zlshift(zI, 1l, &zu);
success = 0;
while (!success) {
do zrandomb(zu, &zR); while (zcompare(zR, zl) < 0);
zmul(zR, zq, &za);
zlshift(za, 1l, &zb);
zsadd(zb, 1l, zn);
zcopy(zR, &za);
zlshift(za, 1l, &zR);
zpstart2();
p = zpnext();
while (zsmod(*zn, p) != 0 && p < B) p = zpnext();
if (p >= B) {
zcopy(*zn, &zc);
zsadd(zc, - 2l, &zb);
do
zrandomb(*zn, &za);
while (zscompare(za, 2l) < 0 || zcompare(za, zb) > 0);
zsadd(*zn, - 1l, &zc);
zexpmod(za, zc, *zn, &zb);
if (zscompare(zb, 1l) == 0) {
zexpmod(za, zR, *zn, &zb);
zcopy(zb, &zd);
zsadd(zd, - 1l, &zb);
zgcd(zb, *zn, &zd);
success = zscompare(zd, 1l) == 0;
}
}
}
}
zfree(&zI);
zfree(&zR);
zfree(&za);
zfree(&zb);
zfree(&zc);
zfree(&zd);
zfree(&zk);
zfree(&zl);
zfree(&zq);
zfree(&zu);
}
void zhorner(long t, long x, verylong zp,
verylong *za, verylong *zf)
{
long i;
verylong zs = 0, zt = 0;
zcopy(za[t - 1], &zs);
for (i = t - 2; i >= 0; i--) {
zsmul(zs, x, &zt);
zadd(zt, za[i], &zs);
}
zmod(zs, zp, zf);
zfree(&zs);
zfree(&zt);
}
void generate(long length, long n, long t,
verylong *zS, verylong *zp, verylong *zs)
{
long i;
verylong *za;
za = calloc(t, sizeof(verylong));
assert(za != 0);
PROVABLE_PRIME(length, zp);
for (i = 0; i < t; i++)
zrandomb(*zp, &za[i]);
for (i = 1; i <= n; i++)
zhorner(t, i, *zp, za, &zS[i - 1]);
zcopy(za[0], zs);
for (i = 0; i < t; i++)
zfree(&za[i]);
free(za);
}
int main(int argc, char *argv[])
{
long i, length, n, t;
verylong zp = 0, zs = 0, *zS;
if (argc != 4) {
fprintf(stderr, "usage: secret length t n\n");
fprintf(stderr, "where length is the bit length\n");
fprintf(stderr, "of the prime number, t is the\n");
fprintf(stderr, "number of users who must pool\n");
fprintf(stderr, "their shadows and n is the total\n");
fprintf(stderr, "number of shares of the secret\n");
exit(1);
}
length = atol(argv[1]);
t = atol(argv[2]);
n = atol(argv[3]);
if (t >= n) {
fprintf(stderr, "error: t must be < n\n");
exit(1);
}
zS = calloc(n, sizeof(verylong));
assert(zS != 0);
generate(length, n, t, zS, &zp, &zs);
printf("%ld\n%ld\n", n, t);
zwriteln(zp);
zwriteln(zs);
for (i = 0; i < n; i++) {
printf("%ld ", i + 1);
zwriteln(zS[i]);
zfree(&zS[i]);
}
free(zS);
zfree(&zp);
zfree(&zs);
return 0;
}
==Pate Williams==
[EMAIL PROTECTED]
http://www.mindspring.com/~pate
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Why the golden ratio?
Reply-To: [EMAIL PROTECTED]
Date: Wed, 14 Jun 2000 18:54:05 GMT
Runu Knips <[EMAIL PROTECTED]> wrote:
: Volker Hetzer wrote:
:>Runu Knips <[EMAIL PROTECTED]> wrote:
:>>AFAIK there is a simple equotation of pi, e, the golden
:>>number, and 1, I don't remember it exactly but it was
:>>really very simple. Maybe I can find it at home.
:>>However, I believe the fact that the golden number is
:>>related to pi and e puts a little of the glory of those
:>>most important numbers into it. :-)
:>
:> It's got nothing to do with pi.
:> It is (sqrt(5)-1)/2.
: Yes, yes, thats its definition. But I've seen once
: a simple nifty equtation in some article in Mr.Dobbs,
: so it is related to pi and e. I think thats the reason
: for it being so popular.
You're /sure/ you're not thinking of the old chestnut of
Euler's equation: e^(iPI) + 1 = 0 ...?
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Be good, do good.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Random sboxes... real info
Reply-To: [EMAIL PROTECTED]
Date: Wed, 14 Jun 2000 18:47:41 GMT
David Hopwood <[EMAIL PROTECTED]> wrote:
: tomstd wrote:
:> Tim Tyler <[EMAIL PROTECTED]> wrote:
:> >So, following the advice of looking at a block cypher and thinking
:> >of it as a large s-box (in the hope of this helping you design
:> >smaller tables) apparently leads to the idea that smaller s-boxes
:> >should be constructed as random permutations...
:>
:> No you failed to see my point.
:>
:> Let's take RC5 with a 128 bit key. There are about 2^128
:> possible permutations right?
:>
:> Well those 2^128 permutations out of the entire (2^64)!
:> permutations are strong with respect to diff and linear
:> analysis.
: I think you may be labouring under a misapprehension - the 2^128
: permutations selected by the key are not stronger than a permutation
: selected at random from the entire space of (2^64)! possibilities.
: In fact, a method for selecting a permutation uniformly at random
: from that space would be as secure as a keyed permutation (a.k.a.
: block cipher) of that size can possibly be.
That last seems questionable. The space of all possible permutations
contains the identity transformation - which is not strong.
A method for selecting a permutation uniformly at random from the space of
all possible permutations would be very, *very* secure - probably much
more secure than any existing block cypher - but ISTM selecting from the
space of *secure* permutations would be likely to produce *fractionally*
better results than selecting from all possible permutations. I believe
the slightly smaller state space is would normally be less of a
disadvantage than retaining the weak transformations.
Of course for a block of any reasonable size, both are totally
impractical.
Also - AFAIK - construction techniques which emulate random permutations
exist - while ones that do so and use a key space which demonstrably
avoids all weak mappings do not.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ This tagline no verb.
------------------------------
Subject: Re: New Idea
From: tomstd <[EMAIL PROTECTED]>
Date: Wed, 14 Jun 2000 12:21:37 -0700
In article <[EMAIL PROTECTED]>, csybrandy
<[EMAIL PROTECTED]> wrote:
>I retract (hehe) what I said before about retireing from the
cipher
>design arena. It seems you can blame Tom for this since I got
this idea
>from reading his paper (which isn't too bad so far)
>
>What gave me this idea was when he stated that data dependent
rotates
>(so far) never use all of the bits in a word. That got me
thinking, how
>would I solve this problem? The first idea I had, assuming 32-
bit
>words, was to extract 6-5 bit values from a single word. This
left us
>with 2 bits unused, so I figured I could do better. Next I
thought
>about 8-4 bit values, but I figured that would be too many try
to use
>and would create a very slow s-box (unless you have hardware
rotates).
>What I finally came up with was creating 4 values by adding
pairs of 4
>bit values from the total of 8. Here's an example:
>
>& = bitwise AND
>>> = right shift
>
>a1 = (A & 15) + ((A >> 4) & 15)
>a2 = ((A >> 8) & 15) + ((A >> 12) & 15)
>a3 = ((A >> 16) & 15) + ((A >> 20) & 15)
>a4 = ((A >> 24) & 15) + ((A >> 28) & 15)
>
>Now if you add the next equation consisting of right rotates
(>>>), left
>rotates (<<<), additions, and exclusive or's (^), you have a
simple
>f-function:
>
>B = B + (A >>> a1) ^ (A <<< a2) + (A >>> a3) ^ (A <<< a4) + k[i]
Hehehehe another weakness.
Suppose a1..a4 were randomly distributed over 0..31 then
0 = (A >>> a1) ^ (A <<< a2)
Would be true for all A iff a1 = 32 - a2
Similarly you get very degenerative properties if a1 = a2 = a3 =
a4 = 0, which is possible if the input A is zero by looking at
>a1 = (A & 15) + ((A >> 4) & 15)
>a2 = ((A >> 8) & 15) + ((A >> 12) & 15)
>a3 = ((A >> 16) & 15) + ((A >> 20) & 15)
>a4 = ((A >> 24) & 15) + ((A >> 28) & 15)
Even with round keys (added to A) you can identify weak keys (a1
= a4) with a prob of 2^-16 and it reveals 16 bits of the key.
The funny thing is because you are not randomly distributed over
0..31 finding
a1 = 32 - a2
Is less probable....
Hehehehe
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: Finding prime numbers
Date: Wed, 14 Jun 2000 15:27:15 -0400
"Tony T. Warnock" wrote:
> > then you need to show that the gap between a prime p and next prime (the
> > number of loop iterations) is bounded by a polynomial in log(p). Now,
> > looking at prime gap tables, that appears to be very likely, but I didn't
> > anyone has proven that.
> >
> > If that has been proven, could someone enlighten me? If you are thinking of
> > a different next-prime algorithm, could you enlighten me?
> >
>
> One does have the theorem that there is a prime between P(k) and 2P(k), also
> there is a prime between P and P**c for (I think) any c>1+epsilon.
Even better: there is a prime between p and p + 1/5p, for primes p > 9.
and there is a prime between p and p + 1/13p for primes p > 11
and even tighter gaps for bigger n.
See
http://www.utm.edu/research/primes/notes/gaps.html
but these gaps are polynomial in p, not log(p).
Define g(p) to be the number of composites between p and the next prime.
There are interesting results and conjectures on bounds of g(p)/log(p).
Again, see
http://www.utm.edu/research/primes/notes/gaps.html
for example.
Anton
------------------------------
From: "John E. Kuslich" <[EMAIL PROTECTED]>
Subject: Re: Cryptanalytic gap [was: Re: Some dumb questions]
Date: Wed, 14 Jun 2000 12:30:01 -0700
No, no...
It is "CRAK". You have used my trademark.
Please cease and desist already.
JK http://www.crak.com Password Recovery Software
JPeschel <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> [EMAIL PROTECTED] writes:
>
> >Here is a simple Casear substitution; solve it:
> >
> >KWBC
>
> If it's a Caesar variant, and the sender's language
> is English: WINO.
>
> J
>
>
> __________________________________________
>
> Joe Peschel
> D.O.E. SysWorks
> http://members.aol.com/jpeschel/index.htm
> __________________________________________
>
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Digits of pi in Twofish
Date: 14 Jun 2000 11:46:10 -0700
In article <[EMAIL PROTECTED]>, Terry Ritter <[EMAIL PROTECTED]> wrote:
>can easily imagine testing a whole raft of mathematical constants to
>find one with particular weakness properties, and then selecting that
>constant for the cipher. But that could never happen, could it?
Well, it'd sure be surprising if the digits of pi happened to have the
required weakness properties, wouldn't it?
--
Matthew Skala, "the modern CEO's worst nightmare" (Macleans, 2000-04-10)
My Internet doesn't include channels, commercials, or the V-chip.
http://www.islandnet.com/~mskala/ [EMAIL PROTECTED]
------------------------------
From: zapzing <[EMAIL PROTECTED]>
Subject: Re: Card Shuffling Protocol
Date: Wed, 14 Jun 2000 19:28:29 GMT
In article <[EMAIL PROTECTED]>,
Baruch Even <[EMAIL PROTECTED]> wrote:
> The algorithm seems to be ok except that you seem to have ommited many
> details off it that should be in the description.
>
> The current shuffler should encrypt everything with his PUBLIC key,
and
> send them to everyone encrypted, when the decided shuffling was
selected
> he should decrypt them all and send it to everyone, they can verify
them
> being correct by encrypting with his public key, if they get the same
things
> he sent before than all is ok, otherwise he lied.
I think you are right. The current shuffler should
take the deck he is given, and in order to create
a shuffling of that deck, should append a random
string to each card and encrypt it using his *Public*
key. Then to prove that a given shuffling is valid,
he would only need to reveal what random strings were
appended to each card.
> Notice though that the protocol carries a large overhead of
computation
> and network transfers. If you denote the number of machines
participating
I agree. If anyone knows of a better one
I would like to know about it.
> by N, the number of extra shuffles chosen by S you get N(N-1)S
messages
> on the network and you need create NS extra shuffles and do N times
the
> fair coin flipping (a coin flipping alone will not do unless you do it
many times
> to choose one of the shuffles).
>
> There is a hole that I thought about now, since everyone knows the
ordering
> it really carries no weight that everyone will shuffle, just choose a
"server" in
> any fair way and execute the card shuffling once. Any more will not
add to
> security since the others can just start from scratch, and your
algorithm will
> not detect it.
If the server and the player who originated the
deck conspired, they could know the entire deck.
If you were playing several hands of poker, say,
then this could mean a significant cheating
possibility. Whenever co-conspirators Mallory
and Nastina were chosen as deck originator and
server they could make a bundle.
> Doing it all only once improves performance considerably.
Yes but this way if *even* *one* of the players
played fair and used a truly random shuffle, then
the output deck would be shuffled randomly.
--
If you know about a retail source of
inexpensive DES chips, please let
me know, thanks.
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
******************************
