145 reputation
17
bio website notyet;)
location Peacedale, RI
age
visits member for 2 years, 8 months
seen 4 hours ago

Electronics Engineer, Amateur Cryptographer with interests in designing real random and psuedorandom bit generators.

"Randomness is like a box of chocolates; you never know what you are going to get"

                                                                   Forrest Gump Jr.

"You can't use mathematical means to create true randomness but you can use mathematical means to stretch a short truly random bitstream into a binary string of virtually infinite length that is indistinguishable from the uniform distribution, the distinguisher being a Universal Turing Machine". John Von Neumann Jr.

"It's trivial to make a Turing machine that fools all other Turing machines into "thinking" that they are looking at an unpredictable uniform distribution. Here is the schematic."

                                                                   Alan Turing Jr.

Apr
9
comment Convert m-Sequence into a de Bruijn Sequence
Thank you fgrieu but I am only interested in designing my own CSPRNG. I only study other designs to see what makes them strong (or fail !). It the reason I took up cryptography as a hobby. :-D
Apr
8
comment Convert m-Sequence into a de Bruijn Sequence
How about another solution? Make a generator consisting of three LFSR's , the outputs of which are XOR'd together , but each LFSR has its own LFSR as a random clock. Sure you will make the key length greater but the added clocking complexity will make attacks like the edit distance attack computationally infeasible. Who knows, maybe some clever mathematician will show that breaking this generator is NP Complete by showing a reduction to 3-SAT. ;-)
Apr
8
comment Convert m-Sequence into a de Bruijn Sequence
A feedback function with a 62 input NOR gate is going to be way too slow for my purposes :-(
Apr
8
comment Convert m-Sequence into a de Bruijn Sequence
Wow, how did you find this? You are fast!!!
Apr
8
comment Convert m-Sequence into a de Bruijn Sequence
Just what I was looking for, you are the best. Not sure what "adding an XOR term equal to the NOR of the outputs of the n-1 flip flops" means??? Say I have a 63 bit register, for an m-sequence I will be tapping tap locations 62 and 63 with a single XOR gate for my feedback function. What am I adding to this to get the de Bruijn sequence?
Apr
8
comment Convert m-Sequence into a de Bruijn Sequence
Nice work but this not show me the electronic real-world circuit for inserting the zeros in the right places! You can't make an actual ASG without a schematic :-(
Apr
8
comment Convert m-Sequence into a de Bruijn Sequence
I don't understand why Gunther says in the paper "it is easy to convert an m-sequence into a deBruijn sequence. To me easy means simple. If you read some of the papers on generating deBruijn sequences, the syntheses are very complicated!!
Apr
8
comment Convert m-Sequence into a de Bruijn Sequence
@fgrieu: My thinking is that Gunther is alluding to a shift register with some kind of nonlinear feedback function consisting of XOR gate(s) with some other nonlinear gate(s), AND, OR, some combination thereof.
Jan
14
comment Can a LFSR be cryptographically secure?
Please be aware that there is an error in the schematic shown in Fig.2 in the Gunther paper "Alternating Step Generator controlled by deBruijn Sequences. The AND gate controlling the clock of the lower shift register is missing an input inverter on the input coming from the deBruijn register. If the circuit was made without the inverter the clocking could not alternate.
Jan
13
comment How to judge if my work is meaningful in cryptography?
@Alex, Just my two cents worth: take your result to a college professor who works in cryptography (hopefully someone in your area) and have him /her critique it before you try and take a "big step" like submitting a paper to a professional journal or a conference.
Dec
25
comment What is the best (thoroughly covering) textbook for application of LFSRs in cryptography?
@Thomas Pornin: It may be premature to be writing-off LFSR's for several reasons. There are several PRNG's based on LFSR's that we have no polynomial time algorithms for breaking (Alternating Step Generator for one). Also nonlinear feedback shift registers is still a relatively new field whose algebraic properties are still not completely understood , so it is a rich field to explore (my opinion).
Dec
11
comment Blum-Blum-Shub Cryptosystem
Richard Feynman once quipped "Nobody understands quantum physics". Well, nobody understands the BBS Cryptosystem either!(kidding). Actually this algorithm is very slow and there are other problems with using it ( see Ritter's Cryptoglossary for a good exposition on this). My advice is to not waste your time with it. Use something else like the Alternating Step Generator as the key generator for a stream cipher. There is no public cryptanalysis (break) for this generator as long as each shift register is 128 bits long.
Dec
1
comment XOR cipher Pseudo-random key strength
@Daniel: How are you "randomly selecting " the predefined characters and how is this table of characters generated? If as you say you don't care that the Mersenne is not cryptographically secure, why worry about the quasi-randomness of your key?
Dec
1
comment XOR cipher Pseudo-random key strength
@Daniel: Your question is related to the object known as a randomness extractor( see Wiki). So I think your question should evolve to something along the lines of "given two sources of weak randomness (1000,5000) and an extraction function A , is applying the function A to (1000) going to create a string of characters with more or less statistical bias than a string created by applying A to (5000).
Nov
30
comment XOR cipher Pseudo-random key strength
Also, there is no known way to mathematically define the "strength" of any particular key string so your question can't be answered on this basis alone.
Oct
31
comment How do I prove that this PRNG is easily distinguished from a random sequence of numbers (modulo m)?
If you can prove that this generator ( or any PRG is indistinguishable from a truly random distribution, you have proven that P is not equal to NP. Go collect your million dollar prize from the Clay Mathematics Institute.
Aug
27
comment Testing the Fortuna random number generator?
@jochen: If you want to test the cryptographic properties you have to see if anyone can "break the generator" by using the output bits to find the secret key.
Jul
12
comment Cryptographic Challenge: How to Say Something Confidentially to Snowden?
There is no reliable substitution for meeting someone in person and exchanging a private key which contains message and identity authentication bits ( I would use 128 bits for each, 256 if you are paranoid and/or smoke weed), in a OTP system or a stream cipher with a known cryptographically secure psuedorandom generator.
Jul
8
comment Are stream ciphers no longer considered by NIST?
Why the Alternating Step Generator is not used more is beyond me, there has been no public cryptanalysis(break) of this generator since it was published in 1987,26 years ago, that is long time to stand up to public scrutiny. It may be un-crackable as long as the key length is large enough, it is an amazingly simple algorithm.
Jun
20
comment Proofs of security methodologies
There are no cryptographic primitives that have proof of security unless you can show that P is not equal to NP. Just showing a reduction from some cryptographic primitive to a known hard problem in NP does not mean that the primitive is secure, you also have to prove that the problem in NP is computationally intractable. That means separating P from NP. This is well known in theoretical computer science.