Generate 20 different bits

Question

I am working on encryption with DES, which uses a 56-bit effective key (after discarding the least significant bits) to encrypt a 64-bit plaintext. I want to set the first 20-bits of the key to random bits, and the last 36-bits to 0. I have been trying to do it with BitSet where I have set up an array with with 64-bits where all the values are false in the beginning. Then I have set up a temp array of 20-bits, and I have been trying to use bitset.set(Random.nextInt(n), true) within a for loop, which goes from 0-20 - The idea is that I get exactly 20 random bits.

In order to discard the least significant bit, I have a for loop where I go from 0 to 20. Within this for loop, I have an if statement which discards every 8th element for the first 20 elements

static BitSet key1 = new BitSet(64);
static BitSet key2 = new BitSet(64);

    public static void generate() {

        BitSet temp1 = new BitSet(20);
        BitSet temp2 = new BitSet(20);

        Random r = new Random();
        for (int i = 0; i < 20; i++) {
            temp1.set(r.nextInt(60), true);
            temp2.set(r.nextInt(60), true);
        }
for (int i = 0; i < 20; i++) {
            key1.set(i, temp1.get(i));
            key2.set(i, temp2.get(i));
        }
            System.out.println(k1temp);

        for (int i = 0; i < temp1.length(); i++) {

        if (i % 8 == 0) {
                key1.clear(i);
                key2.clear(i);
            }
        }    
    }

So, the problem I have is that my BitSet does not always consist of 20 elements, which leads to that the key I generate is wrong. I have been through the code several times, but I cannot see what is wrong.

EDIT:

What I mean by first and last is that the first bits are the Most significant bits and the last are the Least significant bits.

I don't understand what you're trying to do here. Assuming you really want exactly 20 bits, and assuming the first 36 low-order bits are supposed to be zero, why don't you just randomly generate a 20 bit number (which can be easily done with a range parameter to the `Random()` method in Java, just pass it 2^20), and then shift left by 36 bits? That should take about 3 lines of code to implement. — Robert Harvey, Nov 19 '18 at 00:40
@RobertHarvey: After discarding the least significant bits, I want the last 36 bits to be zeros so i have a 56-bit key where the first 20-bit are randomly generated and the last 36-bits are zeros — Bab, Nov 19 '18 at 00:48
And please be clear what you mean by "first" and "last." Use the terms "Most significant" and "least significant," not "first and last" (we don't know at which end of the word you are starting counting bits). — Robert Harvey, Nov 19 '18 at 00:51
By first I mean by first is the Most significant bits and by last is the Least significant bits — Bab, Nov 19 '18 at 01:02
@Bab the root problem described here, is that you repeat `r.nextInt(60)` 2 x 20 times, it is "about" 33%, that you get (at least one) duplicate number from `r.nextInt(60)` (with 50% that it is "the wrong set", so you would override a previously set bit, which makes you missing set bits by the end. — xerx593, Feb 06 '19 at 13:02

Erwin Bolwidt · Answer 1 · 2018-11-19T02:11:16.857

1

You can use bitmasks with the & (bitwise and) operator:

Random r = new SecureRandom(); // WARNING - use SecureRandom when generating cryptographic keys!
long v1 = r.nextLong() & 0xfffff; // Low order 20 bits are random, rest zero
long v2 = r.nextLong() & 0xfffff00000000000L; // High order 20 bits are random

edited Nov 19 '18 at 02:11

answered Nov 19 '18 at 01:03

Erwin Bolwidt

30,799
15
56
79

In case I want to use v2 in DES, do I have to put the v2 in a BitSet of 64 bits as the high order are random? – Bab Nov 19 '18 at 01:09
When using random, sometimes I get less than 64 bits where the high order is 20 bits – Bab Nov 19 '18 at 13:24
Don't use `new java.util.Random` - use `java.security.SecureRandom`. And of course there could be a few leading zero bits - event if it returns zero for those 20 bits, it can still be random (it will happen about once in a million times, on average) – Erwin Bolwidt Nov 20 '18 at 00:29

xerx593 · Answer 2 · 2019-02-11T09:17:34.687

As I understand the problem: You have an unexpected count of (set) bits!

Reason: Using Random, with the given bounds nextInt(60) and a repetition of 2 x 20 times, it is "quite likely" that you set (overwrite) your bits multiple times, which makes you missing (set) bits by the end.

A simple solution 'd be to repeat int next = nextInt(60); until !temp1.get(next) (temp2respectively):

    Random r = new Random();
    for (int i = 0; i < 20; i++) {
        int next = r.nextInt(60);
        while (temp1.get(next)) { //bit already set, repeat:
            next = r.nextInt(60);
        }
        temp1.set(next);

        // temp2:
        next = r.nextInt(60);
        while (temp2.get(next)) {
            next = r.nextInt(60);
        }
        temp2.set(next);
    } // ensures you 20 bits set.

A finer solution, would be a data structure, which ensures you random & unique values...like: Creating random numbers with no duplicates

or this function (see : https://stackoverflow.com/a/54608445/592355):

static IntStream uniqueInts(int min, int max, int count, java.util.Random rnd) {
    // call Random.ints(min, max) with ... distinct and limit
    return rnd.ints(min, max).distinct().limit(count);
}

which you would use like:

final BitSet temp1 = new BitSet(20); // values lower than 64 (resp. 32?) lead to 64 (resp. 32!)
final BitSet temp2 = new BitSet(20);
final Random r = new Random();
unniqueInts(0, 60, 20, r).forEach(i - > {if(i % 8 > 0)temp1.set(i)});
unniqueInts(0, 60, 20, r).forEach(i - > {if(i % 8 > 0)temp2.set(i)});
//also better:
key1.or(temp1);
key2.or(temp2);

System.out.println(k1temp);
//the if (i % 8 == 0)  ..already done in forEach^^

Generate 20 different bits

2 Answers2