From: ichudov@algebra.com (Igor Chudov @ home)
Date: Wed, 11 Dec 1996 07:42:06 -0800 (PST)
To: wichita@cyberstation.net
Subject: Re: IPG algorithim
In-Reply-To: <Pine.BSI.3.95.961211033046.11832G-100000@citrine.cyberstation.net>
Message-ID: <199612111538.JAA00529@manifold.algebra.com>
MIME-Version: 1.0
Content-Type: text


wichita@cyberstation.net wrote:
> 
> 
> 
> Igor, Eric,
> 
> As I have noted to Eric, I appreciate that at least both of you are trying
> to understand and implement the algorithm. My comments follow:
> 
> On Sat, 30 Nov 1996, Igor Chudov @ home wrote:
> 
> > [This is an addition to my previous reply to Eric]
> > 
> > It bugs me that you are using rand() (a fairly lame pseudo-random
> > function that was never intended to be used in cryptographic
> > applications) to seed A, B, C and JV and then test the A(JV) for
> > randomness. Some may object to that. Just for fun, I am attaching a hex
> > dump of output from my /dev/random (Linux 2.0.24). You could simply take
> > these truly random values and put them in initial A, B, C and JV, just
> > to be sure.
> > 
> > I doubt though that your results (poor randomness of A(JV)) will be
> > any different.
> 
> 
> I agree, and as I have indicated elsewhere, either the B or the C is
                                                       ^^^^^^^^^^^^^^^^
> is a prime number. The numbers in A, B, and C are not random numbers,

Don, see my another letter that I sent out last night. What you _need_ 
to require is that C is prime, not B.

Suppose B == p -- some prime number, A == 1, and C == 2*B.

This triplet would fit your criteria, but would be BAD because the only
two numbers it will generate is 1 and P+1.

That would be a rather biased output :)

igor

> they are only selected randomly in a manner almost identical to a LOTTO 
> selections, except that the pools are much larger and the order is
> very significant.
> 
> There are so many things that are wrong with the Murray
> implementation that it would be takes days to clarify it. It is simply not
> the algorithm, nor even any significant part of it. The actual As, Bs and
> Cs are specified at the Web ,site as is the algorithm for using the Key to
> select the ones actually used. In the example, 53 of 512 As, 53 of 600
> plus Bs, and 53 of some 500 plus Cs.
> 
> 
> > 
> > igor
> > 
> > 0000000 c76d 74ac b253 ffc3 ae97 e092 629c 7a53
> > 0000010 087a 21e6 8c2c 0ab6 a03a ea3c 0c71 a748
> > 0000020 68f0 540d a4f2 0a2b b62b 4ab6 ddaa d3e4
> > 0000030 a795 51f3 7dff 067d 2f6b 8d18 fa23 0200
> > 0000040 99df 1d97 e232 b8d5 381f cf1e 7ea8 d971
> > 0000050 8aa0 df0b cf41 53e2 a9f5 5304 dc28 c242
> > 0000060 c01b 5990 75a1 688d 497f cc54 d336 217e
> > 0000070 7dd7 4800 09d4 ff5b 53b8 6308 d38f 60f5
> > 0000080 513a 3ea7 90f6 4cdf e783 6a14 145a e2b1
> > 0000090 2041 6bb5 f417 6109 6101 fecd b7f1 7287
> > 00000a0 f31a 6cb4 d559 ed7c 1be8 e0ca 21f9 8779
> > 00000b0 701e bbcc 8909 7743 bfef c5ef 0f60 cd6a
> > 00000c0 565b 30b5 e710 5f66 aa83 0751 5bc7 867e
> > 00000d0 87a8 8511 9969 d101 c1bb 871b a2e5 f579
> > 00000e0 5e14 9167 480a 9fc2 8354 5769 4ee0 7765
> > 00000f0 faf5 c29f 25ad 77ea 9ecf 39b4 2d11 969f
> > 0000100 099c f85a 7240 9922 0513 d607 41ea ba29
> > 0000110 1886 2611 e577 50c6 87af 393a 782a 6666
> > 0000120 9ae0 221e ec58 ce2e de77 b6de 5821 82e9
> > 0000130 db17 5027 7e57 567a 2e82 f056 01d0 2cde
> > 0000140 0314 ac33 78bd d569 215e b8d7 6a3b 0caa
> > 0000150 b44f 8c6c 04de 4cf2 e111 2803 a073 7d27
> > 0000160 f78c 9d28 70ca 1cd4 ce53 5dea 3141 efa9
> > 0000170 8246 c7ee 4ed3 e49a 8d97 8ded d818 327a
> > 0000180 f999 e044 ff28 ffe9 0254 535c 7e70 a09c
> > 0000190 af58 bcd2 07b0 8146 f4cc 7568 751c c6ee
> > 00001a0 b6b7 be3f d870 84ce 7f8c 3ec4 1427 09fc
> > 00001b0 706e 93f8 9752 230b 74cd 0b0b 38be ba5b
> > 00001c0 a9a6 062a cdee f11d d367 37e2 ec4f 90e4
> > 00001d0 9019 d9ff 2ff9 fb5d 559b 4dd0 2ab0 7e35
> > 00001e0 184a 3e90 f072 7349 007f 5d41 c176 8d8a
> > 00001f0 a30c 1a68 eca6 63f4 256f 88e1 2cec dc1a
> > 0000200 a0ac 90f0 b515 2fbc 2778 4e66 2323 7528
> > 0000210 59c3 c3a9 3ccd e29d 315a fa6a 7821 f6e4
> > 0000220 7977 5e9f df6c f87e 5d15 5693 3da8 9790
> > 0000230 faaf d028 0c05 f5f0 160a 8cb7 f726 18cf
> > 0000240 796d 77c5 3c2e 5ddb f770 7183 3c17 81b7
> > 0000250 b0ff ad01 a4d3 26a1 7821 d210 376a 8283
> > 0000260 3860 61a9 c509 e34c 46a4 7f70 b2ff 18db
> > 0000270 24ad 97b5 e474 eee2 9036 c125 3fdb 88ce
> > 0000280 824a 3096 98fc 0b9f 2f3a 6ac3 25e1 8d08
> > 0000290 46c6 7218 ea87 3c6d 6395 6fc5 34b0 1447
> > 00002a0 ddb3 b3af fdbf b545 5f47 0fe6 bfd0 e799
> > 00002b0 99f6 1fc6 c70b 524f 717f a25d 9f08 f78a
> > 00002c0 e230 b4b9 2045 5652 9677 5ce3 a827 9e8f
> > 00002d0 261f 4650 c731 afbb e257 8410 621a 09aa
> > 00002e0 d991 7a3b bb68 4995 fd15 2afc 8e26 842b
> > 00002f0 cdf7 2d13 4055 9d22 be44 aa16 ed06 db8a
> > 0000300 4210 714b 330d 6c9e 3f81 c993 4d8b 2f6b
> > 0000310 134f 1566 8170 9cc6 4cff d188 78c4 29ae
> > 0000320 27ec 731f 391c 6241 ffaf 2967 8756 1517
> > 0000330 5d1a e807 c477 7757 bd6a ff4c 1cf1 01ce
> > 0000340 dfa7 25b4 5a4f 9cf0 e96e 2d69 0de0 c24e
> > 0000350 0a2c 9ec8 112d 0851 c028 917b b00b f9a0
> > 0000360 0b07 b9f0 c4ef 4426 1cce c8c8 7186 8c24
> > 0000370 9868 fe68 9136 1316 1e58 e883 5aa9 1298
> > 0000380 c0ed eaa4 aaa2 7f23 48d1 5056 8837 06ec
> > 0000390 5f69 ce3a 3d5b 1e7a 7545 e237 352d d887
> > 00003a0 df9c 734d a441 7fa5 6685 eff0 4ce8 1876
> > 00003b0 f9c9 2e18 f825 3a3a a6b8 e0cc 5d49 136a
> > 00003c0 853d dd88 c0f8 befc 8b87 e261 fd73 09af
> > 00003d0 b392 3afa f38e 6a25 cc5d b624 1012 49f3
> > 00003e0 31b0 196c aa02 b3f2 454a 7817 2198 5ad7
> > 00003f0 84c5 f22d 8b6e cdc9 12c3 d0b5 b866 9976
> > 0000400 97a7 3b5e dedf 201d 50f5 99a6 bf54 04ab
> > 0000410 a34e 3a66 538c 51a0 c00b 7ae8 f2ae 6343
> > 0000420 c5f1 1ef1 1f8f 7415 5b50 53a4 33ad d046
> > 0000430 13b6 62a2 cc34 feee 7fda 671a 2b28 a36c
> > 0000440 a806 15be 1ccc b5b9 ef85 04ca 168c 8cd0
> > 0000450 c44e d117 a6c8 cbaf 3b5b 581c d94a 8469
> > 0000460 effb 0f18 cd45 5c77 6ab1 1289 e385 9771
> > 0000470 199f 5610 8095 be8b e257 2ef8 a221 99ee
> > 0000480 1d8b c81c 9781 e803 e4ab 4afb 5669 efb1
> > 0000490 b31f 36e2 5930 b838 e84c 4f6e a709 0c40
> > 00004a0 fefe c530 4ee2 ee3a aa2e e278 de99 8b1e
> > 00004b0 4e83 c98a 47cd 4715 081d 7c7d 5f6f 657c
> > 00004c0 49b5 70c0 937a d4c2 39ff d282 8768 1d7c
> > 00004d0 40fe 1ed1 59b9 d0f7 b4cc 55b3 5da2 4118
> > 00004e0 14dc 4b71 202a fb96 0bed 6d2a 03d6 2f2d
> > 00004f0 9056 8d84 8b6e 948b 4b89 efd1 53ba 9a13
> > 0000500 ea01 770a dc40 fcad bf69 cf60 7884 3f66
> > 0000510 b057 2e82 3745 2839 f68d f637 ad95 5463
> > 0000520 ff3c 353d 08b2 44c2 72bb b25b f60d 0dbf
> > 0000530 455a e9b4 8bbf 3307 071a f720 f00e 0217
> > 0000540 f8cc f7cc 2cc4 ef14 e6b6 7dbc ceff 2dea
> > 0000550 fc34 ed72 d59b 8cd2 794c 2d11 e470 ba44
> > 0000560 bff3 c531 b38b 5398 4a46 63be d86b ae19
> > 0000570 d6a4 2e8d da0d 0ff9 a3db 2cc4 0494 72b1
> > 0000580 b871 1f7e b8da a2f0 2f63 b522 3212 43da
> > 0000590 f910 374e b1f5 5462 8db0 65ef 5e5b 9bf1
> > 00005a0 9337 5003 31fc 47a9 8c06 d0d8 c8ab 8732
> > 00005b0 ff5e 7fe3 b43c 9ba0 14dd f31f cf4c a5b5
> > 00005c0 5552 b1ee 0ee6 a38f dc2b 32ac ab80 e12d
> > 00005d0 be8c ad7d 89e9 5cda 0781 f30c b1d1 3163
> > 00005e0 72f9 bcbe 5972 1862 3a15 660f 4227 b168
> > 00005f0 280d 35fa 1765 46f3 468b 0538 44fc 216e
> > 0000600 30f6 8340 6805 7f5c a280 fcdf 563d 9751
> > 0000610 50c9 fb04 065c 12ec 9ce3 34ee 2a3d f821
> > 0000620 d43e b64e 067f fd26 5e94 b7d1 9b28 fbcf
> > 0000630 811b 4631 6018 5385 1297 e37a b0ea c6fd
> > 
> > Eric Murray wrote:
> > > 
> > > 
> > > 
> > > I have translated the IPG algorithim's "engine" to C, to generate
> > > some random values from it for testing purposes.  It does not
> > > look very random in either the xnoisesph program or the DIEHARD
> > > test battery.   However I may well have misinterprested Mr. Wood's
> > > description (his writing is, as Mr. Chudov points out, difficult to
> > > understand) or written my code incorrectly.  Here it is, play
> > > with it yourself.  To my untrained eye the lack of randomness
> > > in what's essentially a stream cipher would be disturbing.
> > > However I am not a cryptoanalysist so I do not know to
> > > what extent this weakens the cipher.
> > > 
> > > 
> > > The IPG description does not say (but implies to me) that
> > > the various tables that are to be filled in by "random" values must
> > > be filled in by PRNGs that are seeded with the same seeds by
> > > each of the party that knows the key.  Otherwise the "encryptor
> > > streams" that are generated will be unrelated and decryption will not
> > > be possible.  To make my test work I have used the simple rand()
> > > function to fill in the tables.
> > > 
> > > 
> > > Corrections are welcome.
> > > 
> > > 
> > > 
> > > #include <stdio.h>
> > > 
> > > /* a C translation of the IPG "EUREKA" algorithim's "engine".
> > > ** This is supposed to produce random numbers for the IPG
> > > ** "encryptor stream".
> > > ** See http://www.netprivacy.com/ for the original description.
> > > ** Eric Murray  ericm@lne.com  This code placed under GNU copyleft.  */
> > > 
> > > /* machine-dependent stuff, change to suit different platforms: */
> > > typedef unsigned char byte;
> > > typedef unsigned short uint16;
> > > 
> > > 
> > > /* tables: */
> > > uint16 A[53];
> > > uint16 B[53];
> > > uint16 C[53];
> > > 
> > > 
> > > int init_table(uint16*table, uint16 min, uint16 max)
> > > {
> > > 	/* IPG specifies no algorithim for producing the "random"
> > > 	** initial values in the ABC tables, but it's obvious that
> > > 	** it requires a PRNG that's somehow seeded from the "key".
> > > 	** I've just used rand() here.  In UNIX rand() called with no
> > > 	** seed is supposed to seed itself with 0. */
> > > 	int i;
> > > 	int count, r;
> > > 
> > > 	for(i = 0; i < 53; i++) {
> > > 		table[i] = min + (rand() % (max - min));
> > > 	}
> > > }
> > > 
> > > main(int argc, char **argv)
> > > {
> > > 	uint16 jv;
> > > 	int argcnt, i, n, count, diehard, nelem;
> > > 
> > > 	diehard = 0;
> > > 	argcnt = 1;
> > > 	if (argc >= 2) {
> > > 		if (strncmp(argv[argcnt],"-d") == 0) {
> > > 			diehard++;
> > > 			argcnt++;
> > > 		}
> > > 	}
> > > 	if (argc > argcnt - 1 ) {
> > > 		n = atoi(argv[argcnt]);
> > > 		fprintf(stderr,"Generating %d values\n",n);
> > > 	}
> > > 	else {
> > > 		n = 2000;
> > > 	}
> > > 
> > > 	/* seed tables: */
> > > 	fprintf(stderr,"Seeding:  A");  fflush(stderr);
> > > 	init_table(A,0,65535);
> > > 	fprintf(stderr," B");  fflush(stderr);
> > > 	init_table(B,0,12227);
> > > 	fprintf(stderr," C");  fflush(stderr);
> > > 	init_table(C,16384,20361);
> > > 	fprintf(stderr,"\n");  fflush(stderr);
> > > 
> > > 	/* generate n values: */
> > > 	for(; n > 0; n--) {
> > > 		/* jv is "random" (where's it seeded from?) */
> > > 		jv = (uint16)(rand() % 53);
> > > 
> > > 		/* count limits the number of traverses to 53^2 so we don't get stuck */
> > > 		for(count = 0; count < 2809; count++) {
> > > 			jv++;
> > > 			if (jv == 53) jv = 0;
> > > 			A[jv] = (A[jv] + B[jv]) % C[jv];
> > > 			if (A[jv] < 16384) break;
> > > 		}
> > > 		if (count == 2809) fprintf(stderr,"Oops.\n");
> > > 		else {
> > > 			if (!diehard) {
> > > 				printf("%d\n",A[jv]);
> > > 			}
> > > 			else {
> > > 				/* print output in DIEHARD required format:
> > > 				** actually since we have 16-bit ints and DIEHARD
> > > 				** wants 32-bit ints, we print 20 per line instead of 10 */
> > > 				if (nelem++ > 19) {printf("\n"); nelem = 0;}
> > > 				printf("%4.4x",(unsigned int)A[jv]);
> > > 			}
> > > 		}
> > > 	}
> > > }
> > > 
> > > 
> > > 
> > > -- 
> > 
> > 
> > 
> > 	- Igor.
> > 
> 
> With Kindest Regards,
> 
> Don Wood
> 



	- Igor.