Recover the Secret

Phi Comes From Factors

Once the factors are known, phi is no longer hidden.

highlighted = computed this step

Factors give phi

Once p and q are known, phi is computed from p minus one and q minus one.

ϕ=(p−one)(q−one)\phi=(p-\text{one})(q-\text{one})
Phi from recovered factorsThe RSA key table is recomputed from the recovered factors.Phi from recovered factors - n=55quantityvaluep5q11n=p*q55phi=(p-1)(q-1)40e3d=e^-1 mod phi27e*d mod phi1

Subtract one from each factor

The recovered factors give p minus one =4 and q minus one =10.

4,104,10
Phi from recovered factorsThe RSA key table is recomputed from the recovered factors.Phi from recovered factors - n=55quantityvaluep5q11n=p*q55phi=(p-1)(q-1)40e3d=e^-1 mod phi27e*d mod phi1

Multiply to get phi

Multiplying those two values gives phi=40.

4⋅10=404\cdot10=40
Phi from recovered factorsThe RSA key table is recomputed from the recovered factors.Phi from recovered factors - n=55quantityvaluep5q11n=p*q55phi=(p-1)(q-1)40e3d=e^-1 mod phi27e*d mod phi1

Summary

Factoring n exposes the phi value needed to recover d.

ϕ=40\phi=40
Phi from recovered factorsThe RSA key table is recomputed from the recovered factors.Phi from recovered factors - n=55quantityvaluep5q11n=p*q55phi=(p-1)(q-1)40e3d=e^-1 mod phi27e*d mod phi1