A multiplicative inverse is a value that multiplies with another value to produce the multiplicative identity. In modular arithmetic, the target is 1 modulo the modulus: for a value a, an inverse a⁻¹ satisfies a·a⁻¹ ≡ 1 mod m. Unlike ordinary fractions, the inverse is an integer chosen within the modular system. section 2.2.2 section 8.3.2
7 modulo 12
To invert 7 modulo 12, look for an integer whose product with 7 leaves remainder 1 when divided by 12. The answer is 7, because 7 × 7 = 49 and 49 ≡ 1 mod 12. This illustrates why modular inversion is not ordinary division: there is no literal integer fraction 1/7 to use. section 2.2.2
In a linear congruential generator attack, three observed outputs can isolate the multiplier: a ≡ (X₂ − X₁)(X₁ − X₀)⁻¹ mod m. The inverse turns the difference X₁ − X₀ into a factor that can be canceled modulo m, allowing recovery of the generator parameter when the modulus is known. section 2.2.2
Listing 2.9 exploit_lcg.go
import (
"github.com/krkhan/crypto-impl-exploit/ch02/lcg/go/impl_lcg"
"math/big"
)
func findModInverse(a, m int64) int64 {
return new(big.Int).ModInverse(big.NewInt(a), big.NewInt(m)).Int64()
}
Use Go’s math/big ModInverse to compute the modular inverse needed by the multiplier-recovery calculation. section 2.2.2
RSA key generation uses the same operation in a different role. Choose a public exponent e with gcd(e, φ(n)) = 1, then compute the secret exponent d as e⁻¹ mod φ(n). Thus e·d ≡ 1 mod φ(n); the extended Euclidean algorithm computes this inverse efficiently. section 8.3.2
RSA private exponent
With p = 193 and q = 727, φ(n) = 139392. Selecting e = 17653 gives d = 77533, and (17653)(77533) ≡ 1 mod 139392. The public key contains n and e, while d remains secret for decryption. section 8.3.2
