# Re: mp_montgomery_reduce Bug?

*From*: WE@xxxxxxxxxxxxxxxxxx (Wolfgang Ehrhardt)*Date*: Wed, 26 Jan 2011 17:13:38 GMT

On Tue, 25 Jan 2011 12:25:30 -0800 (PST), dilloD <duat66@xxxxxxxxx>

wrote:

Still have not managed to make the values match with the library

cryptopp.

digit_bit cryptopp is also in 32:

const unsigned int * WORD_SIZE WORD_BITS =3D 8, =3D 32

I think I'm doing something wrong.

Let's use the name N for the modulus instead of the long "module". In

most implementations the Montgomery representative of a is Mr(a) = a*R

mod N, where R=2^k normally is a convenient power of two larger than

N. MPArith uses an exponent that is a multiple of DIGIT_BIT.

The Montgomery representative of the a squared mod N is Mr(a^2) =

a^2*R mod N. Since for N=0x90FADE67 the bitsize of N is 32, MPArith

uses two mp_digits for R if DIGIT_BIT=30 or 31 and three mp_digits if

DIGIT_BIT=15, i.e. R is 2^60, 2^62, or 2^45 resp.

With a=0x70F98E5E and N=0x90FADE67 you can calculate Mr(a^2) directly

without invoking mp_montgomery_reduce as

a^2 * 2^60 mod N = 0x4d4e7be5

a^2 * 2^62 mod N = 0x134432c6

a^2 * 2^45 mod N = 0x3b197d29

And these are exactly the values given in my first post.

On the other hand, I found no power of two up to k=200 with

a^2 * 2^k mod N = 0x354910f5, so either Crypto++ is not using this

kind of Montgomery representation, or maybe you do not use it as

intended/specified.

In the Crypto++ docs you find "the Montgomery representation

represents each congruence class [a] as a*r % n, where r is a

convenient power of 2"; therefore the first alternative can be

excluded. Unfortunately the automatically generated docs are rather

Greek for me: maybe s = m.Square(r) assumes a valid Montgomery

representative as argument and/or you should use ConvertIn before

calling it, cf. e.g. function Lucas in nbtheory.cpp.

Anyway, I still have no clue, why you want to tinker with the internal

Montgomery representatives.

Wolfgang

.

**References**:**mp_montgomery_reduce Bug?***From:*dilloD

**Re: mp_montgomery_reduce Bug?***From:*Wolfgang Ehrhardt

**Re: mp_montgomery_reduce Bug?***From:*dilloD

- Prev by Date:
**Re: Motivation for (EC)DSA** - Next by Date:
**Re: mp_montgomery_reduce Bug?** - Previous by thread:
**Re: mp_montgomery_reduce Bug?** - Next by thread:
**Re: mp_montgomery_reduce Bug?** - Index(es):