0
$\begingroup$

Let's say you have a, or several random byte(s) 0-255 and would like to derive numbers 0-9 for a One Time Pad (OTP) of them.

What would be a non-naïve approach to represent 256 possible values onto 10 possible values without weakening the underlying security? I am not sure that I simply can discard 6 states of the 256 values to achieve division by 10 without a fraction as result and not weaken security at the same time.

Is there a simple, yet convincing mathematical approach that I could port myself to a programming language to map bytes into blocks of numbers ranging from 0-9 safely?

Improve this question
$\endgroup$
2
  • $\begingroup$ Derive number from random bytes for OTP?. Just use them as it! $\endgroup$
    – kelalaka
    Jun 20, 2020 at 17:00
  • $\begingroup$ I need it for playing around with One time pads as used by real spies, just think of John le Carré books and movies. $\endgroup$
    – gavery
    Jun 20, 2020 at 22:00

2 Answers 2

Reset to default
4
$\begingroup$

Yes, it is called the simple discard method or rejection sampling. Basically you generate a byte of randomness, then check if the value is equal to or higher than 250 (the highest multiple of 10). If so, you discard the value and regenerate the byte. If you have a value in the range [0, 250) then you simply use modulo 10 (the remainder after the division). And there you are, a well distributed and secure value.

Of course, this method is not very efficient when it comes to a one-time-pad. Generally the one-time-pad is used over bits. But if you have it over digits then it is easier to use 10 to the power of digits you need, then use the simple discard method to generate the larger value, and then perform the (optional) modular reduction. If you take just enough bits, the modular reduction is not needed. After generating the binary value you can perform base conversion to convert the binary value into digits.

If you think the second method is still not efficient enough, then you can use the optimized simple discard method of which I'm the author.

Note that many libraries have both a method to create a large random number in a range as well as methods to get a decimal string, so in that case you can retrieve all required random digits in just two calls (although you may have to convert the character string into values within an integer representing each digit).

Improve this answer
$\endgroup$
5
  • $\begingroup$ Doesn't discarding reduce the entropy? The OP has already random bytes? $\endgroup$
    – kelalaka
    Jun 20, 2020 at 20:51
  • $\begingroup$ It's to be used in a physical one time pad out of nostalgia for old spy books. Which use 0-9 or rarely Latin text with 26 chars. Either is suboptimal when it comes to bytes as source of randomness. It's surprising that discarding really seems to be the way to go, since my problem with it is, that cutting off the distribution from the top >250 or alike would introduce some bias. I'll accept the answer and try to read more about optimized simple discard methods and rejection sampling. $\endgroup$
    – gavery
    Jun 20, 2020 at 22:11
  • $\begingroup$ I think the optimized simple discard method only requires about 2.7 additional bits per value (I should know, I created it :P ). If you really don't like discarding you can create an additional 128 bit, and simply divide. Then the number is only off by a negligible amount. However, for your purpose generating 128 extra bits feels like a lot. $\endgroup$
    – Maarten Bodewes ♦
    Jun 20, 2020 at 22:39
  • 1
    $\begingroup$ Or you can use an integer x and y where 2^x = 10 ^ y ;) $\endgroup$
    – Maarten Bodewes ♦
    Jun 20, 2020 at 22:44
  • $\begingroup$ @kelalaka Yes, if you have a limited amount of entropy then you might want to feed it as seed data into a CSPRNG. $\endgroup$
    – Maarten Bodewes ♦
    Jun 20, 2020 at 22:49
1
$\begingroup$

There can be multiple solutions.

  1. Use decimal representation of each byte. To enable restoring of the original byte stream from 0-9 stream, each 0-9 representation should contain exactly 3 symbols, means, use leading zeroes for numbers less than 100. The transformation would look as follows:
  • 00000000 -> 000
  • 00000001 -> 001
  • 00000010 -> 002
  • 00000011 -> 003
  • ...
  • 00100000 -> 032
  • ...
  • 11111111 -> 255

The frequency of every digit will be not equal, 0 and 1 will have the highest frequency, then 2, then all the others. But this does does not change anything on the entropy of the original data that these 0-9 encoding represents.

The advantage of this approach is that for conversion a single byte at a time is sufficient. For restoring of the byte 3 digits at a time are sufficient.

  1. Use decimal representation of each 4 bits.
  • 0000 -> 00
  • 0001 -> 01
  • 0010 -> 02
  • 0011 -> 03
  • ...
  • 1010 -> 10
  • ...
  • 1111 -> 15

Thus each byte will be represented with 4 digits 0-9.

The advantage is the same as in case with whole byte: For encoding you need 1 byte at a time, for decoding 2 digits 0-9. A disadvantage is, that the result will need more space, 4 digits for each byte instead of 3.

  1. You can use group of bytes, e.g. consider every 2 bytes or every 8 bytes as a decimal number. Don't forget about leading zeroes.

However such groups of bytes would have a disadvantage, that you would need to use padding. E.g. if you use groups of 8 bytes and the last group has less than 8 bytes, this would need extra byte to build a group of 8.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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