12
3
I have designed a simple random generator that cycles two numbers in a chaotic way using a multiply and modulus method. It works great for that.
If I were to use it as a cipher generator it would however be vulnerable to a known plaintext attack, given that an attacker can reverse engineer the seed from a series of random numbers in a computationally efficient manner.
To prove the cipher broken find a legal pair of seed values that generate 7 zeros in a row in the range [0;255], using as little power, CPU-time etc. as possible.
Here is the random generator written in JavaScript:
function seed(state1,state2){
//Constants
var mod1=4294967087
var mul1=65539
var mod2=4294965887
var mul2=65537
function random(limit){
//Cycle each state variable 1 step
state1=(state1*mul1)%mod1
state2=(state2*mul2)%mod2
//Return a random variable
return (state1+state2)%limit
}
//Return the random function
return random
}
//Initiate the random generator using 2 integer values,
//they must be in the ranges [1;4294967086] and [1;4294965886]
random=seed(31337,42)
//Write 7 random values in the range [0;255] to screen
for(a=0;a<7;a++){
document.write(random(256)+"<br>")
}
I have made a tool for testing candidate number pairs, it can be found here.
For the next 3 days, no spoilers allowed, an answer must contain only a set of numbers, and it should of course be a different set from those posted by previous solvers. Thereafter you are encouraged to post code and explain your approach.
Edit, quarantine is over:
Answers should contain both a unique set of numbers and explanation and code to document the solving method.
Most elegant solution wins.
For the record:
Writing a program that can find a solution quickly is elegant.
Making a program that utilize the features of a GPU efficiently to do it even faster is elegant.
Doing the job on a piece of "museumware" is elegant.
Finding a solution method that can feasibly be utilized using only pen and paper is very elegant.
Explaining your solution in an instructive and easily understandable manner is elegant.
Using multiple or very expensive computers is inelegant.
Are you sure an answer exists for this? – Wile E. Coyote – 2011-02-28T00:10:32.310
Yes, there are ~256 of them. And I'm also sure that it's possible to find an answer in a few minutes, given a modern PC and the right programming. – aaaaaaaaaaaa – 2011-02-28T00:50:33.530
Just wondering, why are GPUs elegant but not multiple CPUs? – J B – 2011-03-01T14:07:10.060
Because they are harder to program efficiently than CPUs. You got to make sure that you are actually utilizing the GPU, no points for having most of the shaders idling because some other subsystem is bottlenecking. And of course you still got to implement an efficient algorithm to score the big points. – aaaaaaaaaaaa – 2011-03-01T15:32:29.600
If I submit my working code, it's almost as if I submitted a large bunch of seed pairs. Game end already? – J B – 2011-03-03T08:39:39.060
I'll end it officially 1 week after start and declare a winner. It's the code that is the interesting part of any solution, you really have to post it to make a full answer. And there is definitely still room for some optimizations relative to Keith Randall's answer. Doing some code optimization surely wouldn't hurt you chances of winning. And anyone else may still participate, it takes something better to beat the first submissions, but that is not impossible. – aaaaaaaaaaaa – 2011-03-03T13:12:05.860
this is an awesome question, even though the quarantine is over. thanks for creating this. i look forward to more. – cbrulak – 2011-03-03T21:05:57.807
I'm afraid that I don't have any equally good ideas, I'll post them if I figure something, but no guarantees. – aaaaaaaaaaaa – 2011-03-04T00:58:14.120