Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I read this question about breaking a LCG, but I can't understand how to solve the system of 2 equations given 3 sequential outputs.

The system should be

X2 = (X1 * a + b) mod p
X3 = (X2 * a + b) mod p

How is it possible to find a and b?

I am assuming that X1, X2, X3 and p are known.

share|improve this question

migrated from security.stackexchange.com Jul 13 '12 at 9:34

This question came from our site for Information security professionals.

1  
A related question at scicomp.SE. –  J. M. Jul 13 '12 at 10:03
    
It's two linear equations in two unknowns. I'm sure you know how to solve a system of two linear equations in two unknowns. –  Gerry Myerson Jul 13 '12 at 10:47
add comment

1 Answer

From 'mod', I assume here '=' implies '≡'

Subtracting we get, X2-X3≡a*(X1-X2) (mod p)

If p|(X1-X2), p|b =>p|(X2-2X3)

Else, we can always find an integer c such that c(X1-X2)≡1(mod p) i.e., a modular inverse of (X1-X2) as (p, X1-X2)=1.

Then a≡c(X2-X3)(mod p)

Putting the value of a in one of the given congruence equation, we can get b(mod p).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.