
RM0453 Rev 2
705/1454
RM0453
Public key accelerator (PKA)
721
1.
Inward (or outward) conversion into (or from) Montgomery domain
a) Let’s assume A is an integer in the natural domain
Compute
r2modn
using
Montgomery parameter computation
Result AR= A x
r2modn
mod
n
is A in the Montgomery domain
b) Let’s assume BR is an integer in the Montgomery domain
Result B = BR x 1 mod
n
is B in the natural domain
Similarly, above value AR computed in a) can be converted into the natural
domain by computing A = AR x 1 mod
n
2. Simple modular multiplication A x B mod
n
a) Compute
r2modn
using
Montgomery parameter computation
b) Compute
AR
=
A
x
r2modn
mod
n
. Output is in the Montgomery domain
c) Compute AB= AR x B mod
n
. Output is in natural domain
3. Multiple modular multiplication A x B x C mod
n
a) Compute
r2modn
using
Montgomery parameter computation
b) Compute
AR
=
A
x
r2modn
mod
n
. Output is in the Montgomery domain
c) Compute BR = B x
r2modn
mod
n
. Output is in the Montgomery domain
d) Compute ABR= AR x BR mod
n
. Output is in the Montgomery domain
e) Compute CR = C x
r2modn
mod
n
. Output is in the Montgomery domain
f)
Compute ABCR= ABR x CR mod
n
. Output is in the Montgomery domain
g) (optional) Repeat the two steps above if more operands need to be multiplied
h) Compute ABC= ABCR x 1 mod
n
to retrieve the result in natural domain
Operation instructions for Montgomery multiplication are summarized in
24.4.6 Modular
exponentiation
Modular exponentiation operation is commonly used to perform a single-step RSA
operation. It consists in the computation of A
e
mod
n
.
Operation instructions for modular exponentiation are summarized in
(normal
mode) and in
(fast mode). Fast mode usage is explained in
.
Table 149. Montgomery multiplication
Parameters with direction
Value (Note)
Storage
Size
IN
MODE
0x10
PKA_CR
6 bits
Operand length
(In bits, not null)
RAM@0x404
32 bits
Operand A
(0
≤
A < n)
RAM@0x8B4
ROS
Operand B
(0
≤
B < n)
RAM@0xA44
Modulus value n
(Odd integer only, n < 2
3136
)
RAM@0xD5C
OUT
Result: AxB mod n
(1)
1. Result in Montgomery domain or in natural domain, depending upon the inputs nature (see examples
-
RAM@0xBD0