Folks-- 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?? -fnerd quote me fnerd@smds.com (FutureNerd Steve Witham)
participants (1)
-
fnerd@smds.com