Introduction to Cryptography with Open-Source Software

38 Cryptography with Open-Source Software

stopping when a value of zero is reached. The second column is obtained by

modular squaring, so that

a

i

= a

2

i−1

(mod n).

For the final column:

if k

i

is



even, then m

i

= m

i−1

odd, then m

i

= m

i−1

a

i

.

For the previous example, this produces

i k

i

a

i

m

i

0 1

1 37 83 83 k

1

is odd, so m

1

= m

0

a

1

(mod n)

2 18 13 83 k

2

is even, so m

2

= m

1

(mod n)

3 9 169 84 k

3

is odd, so m

3

= m

2

a

3

(mod n)

4 4 102 84 k

4

is even, so m

4

= m

3

(mod n)

5 2 90 84 k

5

is even, so m

5

= m

4

(mod n)

6 1 78 59 k

6

is odd, so m

7

= m

6

a

6

(mod n)

7 0 k

7

is zero, so stop.

The final m

i

value is the result. This particular format is particularly suitable

for programming.

Modular powers can be ca lcula ...