Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I'm searching for way to generate secure pseudo random sequence with a fixed Hamming weight using a seed. I found below code but I need a seed to generate a sequence ... (and need know if is possible add secure property too . i.e one-way)

from random import shuffle

def gen(ham, bits=32):
    # generate a list with the correct number of 1's
    x = [1]*ham+[0]*(bits-ham)
    shuffle(x)
    # convert back to a number
    return int(''.join(map(str,x)),2)

>> print('\n'.join(bin(gen(5,15)) for x in range(10)))
0b101100100001000
0b100110010010
0b100110110000000
0b10010101100
0b11101100000
0b100100001000110
0b10000010101001
0b110000011100000
0b100011100010
0b100000011100010
share|improve this question

closed as unclear what you're asking by D.W., Gilles, e-sushi, otus, DrLecter Jun 23 at 8:11

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question.If this question can be reworded to fit the rules in the help center, please edit the question.

    
As it stands this question does not meet my quality expectations for this site. In the future please explain in greater detail what you want (e.g., what your specific requirements are), explain the context/motivation, do some research on your own, and show us what research you have done and what you have tried and where you got stuck. And pick just one question: a block cipher is very different from a PRG. P.S. What you want is obviously impossible if the length of the output is equal to the length of the input, as in your example. –  D.W. Jun 21 at 2:08
    
@D.W. I'm edit my question –  juaninf Jun 21 at 14:34
    
with a fixed Hamming weight I'm guessing fixed to a limit of $l$ to a given string $S$? You can generate a string of numbers of length $l$ and use them as an index of where in $S$ the changes will be made. The Hamming distance on its own (as you seem to use it in code) doesn't mean anything, it is a measure of difference of two strings. Apologies if I've missed something in your source code, I'm not familiar with that language. –  rath Jun 21 at 16:53
    
Use the output of a crypto-quality PRG as your seed. Done. Yes, it'll be secure if the PRG is secure. –  D.W. Jun 21 at 17:44

1 Answer 1

up vote 1 down vote accepted

Use a crypto-quality pseudorandom generator PRG (e.g., a stream cipher) to stretch a 128-bit random seed (key) into an unlimited stream of pseudorandom bits. Then, you use it to generate a random $n$-bit string with $k$ bits set.

The latter step is relatively easy. Generate a random integer between $1$ and $C(n,k)$ (inclusive), using your stream of pseudorandom bits. If the integer is $\le C(n-1,k-1)$, then output a 1 as the first bit of output, followed by a $n-1$-bit string with $k-1$ bits set; otherwise, output a 0 as the first bit of output, followed by a $n-1$-bit string with $k$ bits set. The "followed by" part can be done using a recursive call.

See also http://stackoverflow.com/q/2060774/781723.

This construction will be as secure as your PRG, so if you use a crypto-strength PRG, it will be secure.

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.