Hi...
I've attached a test program that spits them out to you.
BTW: Numerical mathematics never was one of my favorites
so my question realy was targeted towards a better
understanding of the libcrypto code.
The only phrase about the multipolication I could find
was that it is an 'modified' multiplication module 2^16+1
where the subblock 0x0000 represents 0x10000.
Ok I understand that a mod multiplication in an ideal
case should be
(a * b) % 0x10001
But what they meant with the subblock 0x0000 being
0x10000 I never understood.
Since the libcrypto is such a well established piece
of software I would be more than happy if the miss-
understanding is all on my side.
On the other hand (at least the IDEA part) is not
very well structured and it is hard to follow the logic
of the code since it seems to be stuffed with all these
macros in an attempt to make it as fast as possible.
Cheers
Sebastian Kloska
Bodo Moeller wrote:
>
> On Thu, Jan 24, 2002 at 03:11:34PM +0100, Sebastian Kloska wrote:
>
> [...]
> > Anyway. After consulting a bunch of crypto books
> > I've stumbled about the idea_mul macro in
> > idea_lcl.h (openssl-0.9.6c) which is supposed
> > to do the modified multiplication mod 2^16+1
> > which looks like.
> >
> > ----------------------------------------------
> >
> > #define idea_mul(r,a,b,ul) \
> > ul=(unsigned long)a*b; \
> > if (ul != 0) \
> > { \
> > r=(ul&0xffff)-(ul>>16); \
> > r-=((r)>>16); \
> > } \
> > else \
> > r=(-(int)a-b+1);
> >
> > ---------------------------------------------
> >
> > All other reference implementations of the
> > multiplication I could find look like:
> >
> > ---------------------------------------------
> > mul( a, b) {
> > int32_t p;
> >
> > if (a)
> > {
> > if (b)
> > {
> > p = a * b;
> > b = p & 0xFFFF;
> > a = p >> 16;
> > return b - a + (b < a);
> > }
> > else
> > return (1 - a);
> > }
> > return (1 - b);
> > }
> > --------------------------------------------
> >
> > And they definitely produce different results.
>
> Can you elaborate? What input values do produce different results?
>
> --
> Bodo Möller <[EMAIL PROTECTED]>
> PGP
http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller/0x36d2c658.html
> * TU Darmstadt, Theoretische Informatik, Alexanderstr. 10, D-64283
Darmstadt
> * Tel. +49-6151-16-6628, Fax +49-6151-16-6036
> ______________________________________________________________________
> OpenSSL Project http://www.openssl.org
> Development Mailing List [EMAIL PROTECTED]
> Automated List Manager [EMAIL PROTECTED]
--
**********************************
Dr. Sebastian Kloska
Head of Bioinformatics
Scienion AG
Volmerstr. 7a
12489 Berlin
phone: +49-(30)-6392-1708
fax: +49-(30)-6392-1701
http://www.scienion.de
**********************************
#include <stdio.h>
#include <sys/types.h>
typedef u_int16_t uint16;
typedef u_int32_t uint32;
typedef u_int32_t word32;
#define low16(a) ((a) & 0xFFFF)
// This macro has been directy copied from the
// libcrypto part (idea_lcl.h) of openssl-0.9.6c
// beside the result r and the arguments a,b it
// needs a tmeporary value ul
// I've just renamed it idea_mul1 instead of idea_mul
//
// This macros itself is part of the E_IDEA macro
// representing the single rounds of the IDEA encryption
// algorithmn (which is called with an argument which
// is never used; BTW: not a very nice and easy
// to follow design). The arguments r,a,b & ul
// seem to be all unsigned longs in the function
// idea_encrypt (i_cbc.c)
//
// When comparing to the other code fragments
// it becomes clear that the
//
// ' +(a<b) '
//
// is omitted.
#define idea_mul1(r,a,b,ul) \
ul=(unsigned long)a*b; \
if (ul != 0) \
{ \
r=(ul&0xffff)-(ul>>16); \
r-=((r)>>16); \
} \
else \
r=(-(int)a-b+1); /* assuming a or b is 0 and in range */ \
// this one is taken from Bruce Schneiers Book (Applied Crypto)
// as can be found under
//
// http://www.ee.udel.edu/~mills/database/schneier/disk1/
//
// It however contained a typo
//
// It used to be:
// ....
// if(a)
// return 1-b
// else
// return 1-a;
//
// but in this case the method would always return 1
// since if a!=0 b has to be zero (since p has been tested to be zero)
// and 1-b would always result in 1. On the other hand if a==0 1-a also
// results in 1
uint16 idea_mul2(register uint16 a, register uint16 b)
{
register word32 p;
p = a * b;
if (p) {
b = low16(p);
a = p >> 16;
return (b - a) + (b < a);
} else if (a) {
return 1-a;
} else {
return 1-b;
}
}
// This piece of code is ruthelessly taken
// from the Crypto-IDEA perl code.
//
// Both code fragments assume that
// the expressiion (b<a) returns an
// expression which is suitable for
// addition (namely 0 and 1) which
// I think is an assumption not
// covered by any standard but it
// makes the code look more hacker style... ;-)
//
uint16 idea_mul3( u_int16_t a, u_int16_t b) {
u_int32_t p;
if (a)
{
if (b)
{
p = a * b;
b = p & 0xFFFF;
a = p >> 16;
return b - a + (b < a);
}
else
return (1 - a);
}
return (1 - b);
}
char *waiting="-\\|/";
int main() {
uint16 a;
uint16 b;
uint16 r1,r2;
uint32 ul;
uint32 z;
int j;
fprintf(stderr," -- checkin idea_mul1 against idea_mul2\n");
a=0;
b=0;
do {
do {
idea_mul1(r1,a,b,ul);
r2=idea_mul3(a,b);
if(r1!=r2)
fprintf(stderr," ?? r1!=r2 (a=0x%04x,b=0x%04x) (r1=0x%04x,r2=0x%04x)}
\n",a,b,r1,r2);
} while(++a != 0xFFFF);
} while(++b != 0xFFFF);
fprintf(stderr,"checkin idea_mul2 against idea_mul3\n");
a=0;
b=0;
z=0;
j=0;
do {
do {
r1 = idea_mul2(a,b);
r2 = idea_mul3(a,b);
if(r1!=r2)
fprintf(stderr," ?? r1!=r2 (a=0x%04x,b=0x%04x) (r1=0x%04x,r2=0x%04x)
\n",a,b,r1,r2);
// print out something every 100000 iterations
//
if(z++ % 100000) {
fprintf(stderr,"%c\r",waiting[j++]);
if(j>3)
j=0;
}
} while(++a != 0xFFFF);
} while(++b != 0xFFFF);
}
______________________________________________________________________
OpenSSL Project http://www.openssl.org
Development Mailing List [EMAIL PROTECTED]
Automated List Manager [EMAIL PROTECTED]
