peasant_multiply question

FutureNerd Steve Witham fnerd at
Tue Dec 8 09:53:58 PST 1992


I got out my copy of the original RSA paper, and I'm comparing it to the
PGP 2.0 code.  I have a question about the peasant_modmult routine (the
simplest modmult in PGP).  Here's pseudocode of what I think it's doing:

    /* Inputs: modulus, multiplier, multiplicand */
    /* Output: prod */

    prod = 0;
    set sniffer to most significant bit of multiplier;
    nbits = number of significant bits in multiplier;

    while( nbits-- )
        shift prod left 1;
        prod = prod - modulus;
        if( the bit of the multiplier being sniffed = 1 )
            prod = prod + multiplicand;
            prod = prod - modulus;
        move the sniffer to the next bit of the multiplier;

My question is (assuming I'm understanding the code right), how can it
work subtracting modulus unconditionally all the time?  Won't it make
prod negative sometimes, and then keep multiplying the negative number
by two until it overflows?   Isn't that a problem??

quote me
fnerd at (FutureNerd Steve Witham)

More information about the cypherpunks-legacy mailing list