Is this a school assignment? It is of good manners to state that outright in your first post.

Shuffle algorithms can handle this easily, although those may fail with sufficiently large N and K that won't fit in memory.  Several unbiased O(n) shuffle algorithms exist, such as the Fisher-Yates shuffle. If you're using C++ there is an implementation of that std::shuffle() which was previously known as std::random_shuffle() if you're using an old compiler.

Even if you can't hold N in memory, if you could hold a count of N values in an array then it becomes your index into N. Add values from 0 to N-1 as all index values, shuffle them, and pick K values.

If you can't reasonably make a list of length N, this comes to mind:

1. Select random offset numbers. Select K numbers; pull from 0 to N-1, then from 0 to N-2, then from 0 to N-3.  etc.   Use a non-biased algorithm for this.
2. Compute the index values.  Iterate through the offset numbers.  The initial value is the random number, then iterate over the prior index values in ascending order; if an existing index value is lower than the value you are considering, increment your current value under consideration. When you've incremented up to the current value, it becomes the new index.  In other words, the offset value means to advance that many unused numbers.
3. Look up the index values from pool N for the final list.

As an example of N=15 and K=5:

1. Using a random number generator I get the following five values from the first step: { 1, 9, 4, 11, 6 }

2. Next I compute the index values:

Index 1. { 1 }

Offset 9 finds it is greater then index 1, so becomes index 10 { 1, 10 }

Offset 4 finds it is greater than index 1, 10 is greater, so becomes index 5. { 1, 5, 10 }

Offset 11 finds it is greater than 1, 5, and 10, so becomes index 14. { 1, 5, 10, 14 }

Offset 6 finds it is greater than 1 and 5, so becomes index 8. { 1, 5, 8, 10, 14 }

3. Look up the values N[1], N[5], N[8], N[10], N[14].  This is your result.

If ordering were important, maintain a parallel ordered list where each index is added in the same order they were generated from the initial offset list.

And for N=15 and K=15 so you should see every item:

Offset numbers { 1 9 4 11 6 4 6 7 2 3 2 0 2 0 0 }

Index values as they grow:

(unused offset 1) 1
(+9) 1 10
(+4) 1 5 10
(+11) 1 5 10 14
(+6) 1 5 8 10 14
(+4) 1 5 6 8 10 14
(+6) 1 5 6 8 10 11 14
(+7) 1 5 6 8 10 11 13 14
(+2) 1 3 5 6 8 10 11 13 14
(+3) 1 3 5 6 7 8 10 11 13 14
(+2) 1 3 4 5 6 7 8 10 11 13 14
(+0) 0 1 3 4 5 6 7 8 10 11 13 14
(+2) 0 1 3 4 5 6 7 8 10 11 12 13 14
(+0) 0 1 2 3 4 5 6 7 8 10 11 12 13 14
(+0) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

If you want that in random order, preserve the order of the offsets:  { 1 10 5 14 8 6 11 13 3 7 4 0 12 2 9 }

Or if you prefer to see it from the perspective of the UNUSED pool:

(position 1) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
(9) 0 2 3 4 5 6 7 8 9 10 11 12 13 14
(4) 0 2 3 4 5 6 7 8 9 11 12 13 14
(11) 0 2 3 4 6 7 8 9 11 12 13 14
(6) 0 2 3 4 6 7 8 9 11 12 13
(4) 0 2 3 4 6 7 9 11 12 13
(6) 0 2 3 4 7 9 11 12 13
(7) 0 2 3 4 7 9 12 13
(2) 0 2 3 4 7 9 12
(3) 0 2 4 7 9 12
(2) 0 2 4 9 12
(0) 0 2 9 12
(2) 2 9 12
(0) 2 9
(0) 9

I'm pretty sure that would generate a biased distribution rather than a random distribution.  Also, the multi-round RSA thing is going to be rather complex.

#include <iostream>

int C[20][20] = {0};

void print_combination(int r, int n, int k) {
  if (k == 0)
    return;
  bool selected = (r < C[n-1][k-1]);
  if (selected) {
    print_combination(r, n-1, k-1);
    std::cout << n << ' ';
  }
  else
    print_combination(r - C[n-1][k-1], n-1, k);
}

int main() {
  // Initialize combinatorial numbers table                                                                                               
  for (int i = 0; i < 20; ++i) {
    C[i][0] = 1;
    for (int j = 1; j <= i; ++j)
      C[i][j] = C[i-1][j-1] + C[i-1][j];
  }

  // Loop over all combinations                                                                                                           
  for (int x = 0; x < C[6][3]; ++x) {
    print_combination(x, 6, 3);
    std::cout << '\n';
  }
}

For your original question, call `print_combination(random_number, 6, 3)'.

Also see the constraint: - N and K are very big - I mean, you can't iterate all the possibilities

3 minutes ago, frob said:

Also see the constraint: - N and K are very big - I mean, you can't iterate all the possibilities

If you were referring to my code, the iteration over all possibilities is for demonstration purposes only. The function print_combination would work for large N and K (as long as you can handle numbers as big as C[N][K], which is assumed as part of the original post).

EDIT: It can also be done non-recursively, but I think the code is easier to understand in this version.