Fast Exponentiation

Modexp RSA Decrypt

Use square-and-multiply for RSA decryption. This is toy arithmetic only, not deployable security.

Example

Use square-and-multiply for RSA decryption.

highlighted = computed this step

Step 1 — Set up

Set up the exact toy cryptography values.

base, exponent, modulus(13, 27, 55)\begin{array}{c|c}\text{base, exponent, modulus}&\text{(13, 27, 55)}\end{array}

Step 2 — Bit 1

Compute the highlighted cryptography value.

bit, raw square, square mod m, raw multiply, multiply mod m, residue(1, 1, 1, 13, 13, 13)\begin{array}{c|c}\text{bit, raw square, square mod m, raw multiply, multiply mod m, residue}&\hlmath{\text{(1, 1, 1, 13, 13, 13)}}\end{array}

Step 3 — Bit 2

Compute the highlighted cryptography value.

bit, raw square, square mod m, raw multiply, multiply mod m, residue(1, 169, 4, 52, 52, 52)\begin{array}{c|c}\text{bit, raw square, square mod m, raw multiply, multiply mod m, residue}&\hlmath{\text{(1, 169, 4, 52, 52, 52)}}\end{array}

Step 4 — Bit 3

Compute the highlighted cryptography value.

bit, raw square, square mod m, raw multiply, multiply mod m, residue(0, 2704, 9, -, -, 9)\begin{array}{c|c}\text{bit, raw square, square mod m, raw multiply, multiply mod m, residue}&\hlmath{\text{(0, 2704, 9, -, -, 9)}}\end{array}

Step 5 — Bit 4

Compute the highlighted cryptography value.

bit, raw square, square mod m, raw multiply, multiply mod m, residue(1, 81, 26, 338, 8, 8)\begin{array}{c|c}\text{bit, raw square, square mod m, raw multiply, multiply mod m, residue}&\hlmath{\text{(1, 81, 26, 338, 8, 8)}}\end{array}

Step 6 — Bit 5

Compute the highlighted cryptography value.

bit, raw square, square mod m, raw multiply, multiply mod m, residue(1, 64, 9, 117, 7, 7)\begin{array}{c|c}\text{bit, raw square, square mod m, raw multiply, multiply mod m, residue}&\hlmath{\text{(1, 64, 9, 117, 7, 7)}}\end{array}

Final Step — Result

Compute the highlighted cryptography value.

result7\begin{array}{c|c}\text{result}&\hlmath{\text{7}}\end{array}
cryptography The values in this lesson are deliberately tiny so every modular arithmetic step can be checked exactly.