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.

Problem details:

Let $p = 2^{48}$, $s\leftarrow\{0,1\}^{48}$, and $a,b$ known constants.

Furthermore let $f(x) = a x + b \pmod{p}$

and let the value $r_k$ be defined by the first-order recurrence relation:

$r_0 = s$

$r_i = f(f(r_{i-1}))$.

Suppose we are given a sequence of values $V = [c(r_1), c(r_2), ... , c(r_n)]$

where we can think of $c(x)$ as a bit mask that reveals only the 6 most significant bits of some bit string $x$.

Question:

How long does $V$ need to be in order to solve for $s$?

Background:

Some implementations of Javascript use a Linear Congruential Generator (LCG) for the Math.random() built-in function. I'd like to see if, given a masked sequence of outputs from Math.random(), I can infer the internal state of the LCG, and thus be able to predict future masked values. If so, how many values do I need to do this?

My educated guess/approach:

I've been racking my brain/whiteboard about this problem all weekend, but I feel uncomfortable trying to reason about modular arithmetic.

I would think that with each $r_i$ we gain at least a little information about the internal state. Since we need to learn about a 48-bit number, and we learn only 6 bits per $r_i$, we probably need at least 8 values ($6*8 = 48$) before it's possible to completely infer $s$. In my specific case I get an average of 30 consecutive values, which I would think would be plenty.

One promising idea that I had last night was to think of each $c(r_i)$ as denoting an inequality over the range of possible $r_i$ values, and then solve for some system of modular inequalities-- which I have no idea how to do.

share|improve this question
    
Also, is this the right board for this question? –  machine yearning Feb 4 '13 at 21:14
2  
I'm not familiar with the details of the algorithm, but you might want to look up Håstad and Shamir's paper "The Cryptographic Security of Truncated Linearly related Variables". It looks like this paper and the related "Reconstructing Truncated Integer Variables..." are available on Håstad's web page. –  Erick Wong Feb 4 '13 at 21:22
    
@ErickWong Thanks, I actually appreciate the references more than an answer =) –  machine yearning Feb 4 '13 at 21:24
    
Do you really mean $f(f(r_{i-1}))$, not $f(r_{i-1})$? Running $f$ twice at each iteration is the same as running some other linear function $g$ once, anyway. –  Gerry Myerson Feb 5 '13 at 3:10
    
@GerryMyerson: According to this article the generator is advanced twice per value generated; but I do see your point, perhaps that will help simplify my deduction process later. Thanks! –  machine yearning Feb 5 '13 at 5:51
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.