The Ladder

RSA/DH Reuse

The same modular exponentiation shape appears in RSA and Diffie-Hellman. This book keeps the claim to exact arithmetic over toy inputs.

highlighted = computed this step

Why this shows up again

RSA and Diffie-Hellman reuse this arithmetic shape with different pinned inputs.

be mod mb^e\bmod m
Reusable arithmeticThe ladder rows are recomputed from pinned base, exponent, and modulus.Reusable arithmetic - 7^13 mod 33stepbitpriorsquaremultiplyresult01117711716131320134skip4314161313

Name the reusable shape

The shape is base 7 to exponent 13 modulo 33, evaluated by the same square-and-multiply rows.

713 mod 337^{13}\bmod{}33
Reusable arithmeticThe ladder rows are recomputed from pinned base, exponent, and modulus.Reusable arithmetic - 7^13 mod 33stepbitpriorsquaremultiplyresult01117711716131320134skip4314161313

What changes later

Later books change the base, exponent, or modulus. The trust boundary still recomputes the same kind of ladder before displaying a result.

new inputs, same recompute\text{new inputs, same recompute}
Reusable arithmeticThe ladder rows are recomputed from pinned base, exponent, and modulus.Reusable arithmetic - 7^13 mod 33stepbitpriorsquaremultiplyresult01117711716131320134skip4314161313

Toy numbers only

The modulus 33 is small so the arithmetic can be inspected. NOTE: toy-modulus; no-production; never-roll-your-own. This is not a secure modulus.

m=33m=33
Reusable arithmeticThe ladder rows are recomputed from pinned base, exponent, and modulus.Reusable arithmetic - 7^13 mod 33stepbitpriorsquaremultiplyresult01117711716131320134skip4314161313

What this model excludes

NOTE: no-padding; no-side-channel; no-production; never-roll-your-own. This lesson models exact arithmetic only; padding, timing, side channels, and key security are outside this static table.

arithmetic only\text{arithmetic only}
Reusable arithmeticThe ladder rows are recomputed from pinned base, exponent, and modulus.Reusable arithmetic - 7^13 mod 33stepbitpriorsquaremultiplyresult01117711716131320134skip4314161313

Summary

The reusable fact is the exact ladder result 13.

result=13\text{result}=13
Reusable arithmeticThe ladder rows are recomputed from pinned base, exponent, and modulus.Reusable arithmetic - 7^13 mod 33stepbitpriorsquaremultiplyresult01117711716131320134skip4314161313