Funzione inversa della funzione Random di Java

Question

La funzione Random di Java prende un seme e produce una sequenza di numeri "psuedo-random". (È implementato in base ad alcuni algoritmi discussi in Donald Knuth, The Art of Computer Programming, Volume 3, Section 3.2.1.), ma l'articolo è troppo tecnico per me da comprendere)

Esiste una funzione inversa? Cioè, data una sequenza di numeri, sarebbe possibile determinare matematicamente quale sarebbe il seme? (che significa, bruta costringendo non conta come un metodo valido)

[Edit] Sembra che ci sia un certo numero di commenti qui ... ho pensato di chiarire quello che sto cercando .

Ad esempio, la funzione y = f(x) = 3x ha una funzione inversa, ovvero y = g(x) = x/3.

Ma la funzione z = f(x, y) = x * y non ha una funzione inversa, perché (ho potuto dare una piena dimostrazione matematica qui, ma non voglio di depistare la mia domanda principale), intuitivamente parlando, ci sono più di un paio di (x, y) tale che (x * y) == z.

Ora tornando alla mia domanda, se si dice che la funzione non è inversione, si prega di spiegare perché.

(E io sto sperando di ottenere risposte da coloro che hanno realmente letto l'articolo e capire. Le risposte del tipo "E 'solo non è possibile" non sono realmente aiutando)

Answer 1

io normalmente non solo collegare articoli ... Ma ho trovato un sito in cui qualcuno ci esamina in profondità e ha pensato che valesse la pena postare. http://jazzy.id.au/default/2010/09/20/cracking_random_number_generators_part_1.html

Sembra che è possibile calcolare un seme in questo modo:

seed = (seed * multiplier + addend) mod (2^precision) 

dove moltiplicatore è 25.214.903,917 mila, addendi è 11, e la precisione è 48 (bit). Non è possibile calcolare quale fosse il seed con solo 1 numero, ma è possibile con 2.

EDIT: Come nhahtdh ha detto che c'è una parte 2 in cui approfondisce la matematica dietro i semi.

Answer 2

Vorrei presentare un'implementazione per invertire una sequenza di numeri interi generati da nextInt().

Il programma eseguirà la forza bruta sul 16 bit inferiore scartato da nextInt(), utilizzerà l'algoritmo fornito nel blog da James Roper per trovare il seme precedente, quindi verificare che i 32 bit superiori del seme a 48 bit siano gli stessi di il numero precedente. Sono necessari almeno gli interi per ricavare il seme precedente. Altrimenti, ci saranno 2 possibilità per il seme precedente, e tutte sono ugualmente valide finché non abbiamo almeno un altro numero.

può essere esteso per nextLong() facilmente, e long numero è sufficiente per trovare il seme, dal momento che abbiamo 2 pezzi di superiore a 32 bit del seme in una long, due to the way it is generated.

Si noti che in alcuni casi il risultato non è uguale a quello impostato come seme segreto nella variabile SEED.Se il numero impostato come seme segreto occupa più di 48 bit (ovvero il numero di bit utilizzati per generare numeri casuali internamente), i 16 bit superiori di 64 bit di long verranno rimossi nel metodo setSeed(). In questi casi, il risultato restituito non sarà uguale a quello impostato inizialmente, è probabile che il valore più basso di 48 bit sia lo stesso.

Vorrei dare più credito a James Roper, l'autore di this blog article che rende il codice di esempio riportato di seguito possibile:

import java.util.Random; 
import java.util.Arrays; 

class TestRandomReverse { 
    // The secret seed that we want to find 
    private static long SEED = 782634283105L; 

    // Number of random numbers to be generated 
    private static int NUM_GEN = 5; 

    private static int[] genNum(long seed) { 
    Random rand = new Random(seed); 
    int arr[] = new int[NUM_GEN]; 
    for (int i = 0; i < arr.length; i++) { 
     arr[i] = rand.nextInt(); 
    } 

    return arr; 
    } 

    public static void main(String args[]) { 

    int arr[] = genNum(SEED); 
    System.out.println(Arrays.toString(arr)); 

    Long result = reverse(arr); 

    if (result != null) { 
     System.out.println(Arrays.toString(genNum(result))); 
    } else { 
     System.out.println("Seed not found"); 
    } 
    } 

    private static long combine(int rand, int suffix) { 
    return (unsignedIntToLong(rand) << 16) | (suffix & ((1L << 16) - 1)); 
    } 

    private static long unsignedIntToLong(int num) { 
    return num & ((1L << 32) - 1); 
    } 

    // This function finds the seed of a sequence of integer, 
    // generated by nextInt() 
    // Can be easily modified to find the seed of a sequence 
    // of long, generated by nextLong() 
    private static Long reverse(int arr[]) { 
    // Need at least 2 numbers. 
    assert (arr.length > 1); 

    int end = arr.length - 1; 

    // Brute force lower 16 bits, then compare 
    // upper 32 bit of the previous seed generated 
    // to the previous number. 
    for (int i = 0; i < (1 << 16); i++) { 
     long candidateSeed = combine(arr[end], i); 
     long previousSeed = getPreviousSeed(candidateSeed); 

     if ((previousSeed >>> 16) == unsignedIntToLong(arr[end - 1])) { 
     System.out.println("Testing seed: " + 
          previousSeed + " --> " + candidateSeed); 

     for (int j = end - 1; j >= 0; j--) { 
      candidateSeed = previousSeed; 
      previousSeed = getPreviousSeed(candidateSeed); 

      if (j > 0 && 
      (previousSeed >>> 16) == unsignedIntToLong(arr[j - 1])) { 
      System.out.println("Verifying: " + 
           previousSeed + " --> " + candidateSeed); 
      } else if (j == 0) { 
      // The XOR is done when the seed is set, need to reverse it 
      System.out.println("Seed found: " + (previousSeed^MULTIPLIER)); 
      return previousSeed^MULTIPLIER; 
      } else { 
      System.out.println("Failed"); 
      break; 
      } 
     } 
     } 
    } 

    return null; 
    } 

    private static long ADDEND = 0xBL; 
    private static long MULTIPLIER = 0x5DEECE66DL; 

    // Credit to James Roper 
    // http://jazzy.id.au/default/2010/09/21/cracking_random_number_generators_part_2.html 
    private static long getPreviousSeed(long currentSeed) { 
    long seed = currentSeed; 
    // reverse the addend from the seed 
    seed -= ADDEND; // reverse the addend 
    long result = 0; 
    // iterate through the seeds bits 
    for (int i = 0; i < 48; i++) 
    { 
     long mask = 1L << i; 
     // find the next bit 
     long bit = seed & mask; 
     // add it to the result 
     result |= bit; 
     if (bit == mask) 
     { 
     // if the bit was 1, subtract its effects from the seed 
     seed -= MULTIPLIER << i; 
     } 
    } 

    return result & ((1L << 48) - 1); 
    } 
} 

Answer 3

Se stiamo parlando della Oracle (nata Sun) l'attuazione di java.util.Random , allora sì, è possibile una volta che conosci abbastanza bit.

Random utilizza un seme a 48 bit e un generatore congruenziale lineare. Questi non sono generatori crittograficamente sicuri, a causa delle minuscole dimensioni dello stato (bruteforceable!) E del fatto che l'output non è casuale (molti generatori esibiranno una piccola lunghezza del ciclo in alcuni bit, il che significa che questi bit possono essere facilmente predetti anche se gli altri bit sembrano casuali). aggiornamento seme

Random 's è la seguente:

nextseed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1) 

Questa è una funzione molto semplice, e può essere invertito se si conosce tutti i bit del seme calcolando

seed = ((nextseed - 0xBL) * 0xdfe05bcb1365L) & ((1L << 48) - 1) 

dal 0x5DEECE66DL * 0xdfe05bcb1365L = 1 mod 2 . Con questo, un singolo valore di seme in qualsiasi momento è sufficiente per recuperare tutti i semi passati e futuri.

Random non ha funzioni che rivelano l'intero seme, però, quindi dovremo essere un po 'intelligenti.

Ora, ovviamente, con un seme a 48 bit, è necessario osservare almeno 48 bit di output o chiaramente non si dispone di una funzione iniettiva (e quindi invertibile) con cui lavorare. Siamo fortunati: nextLong restituisce ((long)(next(32)) << 32) + next(32);, quindi produce 64 bit di output (più del necessario). In effetti, potremmo probabilmente accontentarci di nextDouble (che produce 53 bit) o ​​semplicemente di chiamate ripetute di qualsiasi altra funzione. Si noti che queste funzioni possono non emette più di 2 valori unici a causa delle limitate dimensioni del seme (quindi, per esempio, ci sono 2 -2 long s che nextLong sarà mai produrre).

Diamo un'occhiata in particolare a nextLong. Restituisce il numero (a << 32) + b dove a e sono entrambe quantità a 32 bit. Lasciare s essere il seme prima che venga chiamato nextLong. Quindi, lasciare t = s * 0x5DEECE66DL + 0xBL, in modo che a sia i 32 bit alti di t e lasciare u = t * 0x5DEECE66DL + 0xBL in modo che b siano i 32 bit alti di u. Sia c e d i 16 bit bassi di t e u rispettivamente.

Si noti che dal c e dal d sono quantità di 16 bit, possiamo solo rinforzarli (poiché ne abbiamo solo bisogno) e utilizzarli. È piuttosto economico, dal momento che il numero 2 è solo 65536 - piccolo per un computer.Ma siamo un po 'più intelligenti e vediamo se c'è un modo più veloce.

Abbiamo (b << 16) + d = ((a << 16) + c) * 0x5DEECE66DL + 11. Così, facendo qualche algebra, otteniamo (b << 16) - 11 - (a << 16)*0x5DEECE66DL = c*0x5DEECE66DL - d, mod 2 . Poiché c e d sono entrambe le quantità a 16 bit, c*0x5DEECE66DL ha al massimo 51 bit. Ciò significa utilmente che

(b << 16) - 11 - (a << 16)*0x5DEECE66DL + (k<<48) 

è pari a c*0x5DEECE66DL - d per qualche k al massimo 6. (Ci sono modi più sofisticati per calcolare c e d, ma perché il legato sulla k è così piccolo, è più facile da solo bruteforce) .

Possiamo verificare appena tutti i valori possibili per k fino ad ottenere un valore whos negati restante mod 0x5DEECE66DL è di 16 bit (mod 2 nuovo), in modo da recuperare i 16 bit inferiori di entrambi t e u. A quel punto, abbiamo un seme completo, quindi possiamo trovare i semi futuri usando la prima equazione o i semi passati usando la seconda equazione.

codice che illustrano l'approccio:

import java.util.Random; 

public class randhack { 
    public static long calcSeed(long nextLong) { 
     final long x = 0x5DEECE66DL; 
     final long xinv = 0xdfe05bcb1365L; 
     final long y = 0xBL; 
     final long mask = ((1L << 48)-1); 

     long a = nextLong >>> 32; 
     long b = nextLong & ((1L<<32)-1); 
     if((b & 0x80000000) != 0) 
      a++; // b had a sign bit, so we need to restore a 
     long q = ((b << 16) - y - (a << 16)*x) & mask; 
     for(long k=0; k<=5; k++) { 
      long rem = (x - (q + (k<<48))) % x; 
      long d = (rem + x)%x; // force positive 
      if(d < 65536) { 
       long c = ((q + d) * xinv) & mask; 
       if(c < 65536) { 
        return ((((a << 16) + c) - y) * xinv) & mask; 
       } 
      } 
     } 
     throw new RuntimeException("Failed!!"); 
    } 

    public static void main(String[] args) { 
     Random r = new Random(); 
     long next = r.nextLong(); 
     System.out.println("Next long value: " + next); 
     long seed = calcSeed(next); 
     System.out.println("Seed " + seed); 
     // setSeed mangles the input, so demangle it here to get the right output 
     Random r2 = new Random((seed^0x5DEECE66DL) & ((1L << 48)-1)); 
     System.out.println("Next long value from seed: " + r2.nextLong()); 
    } 
}