जावा के रैंडम फ़ंक्शन का उलटा फ़ंक्शन

Question

जावा का रैंडम फ़ंक्शन बीज लेता है और 'psuedo-random' संख्याओं का अनुक्रम बनाता है। (यह Donald Knuth, The Art of Computer Programming, Volume 3, Section 3.2.1.) में चर्चा की गई कुछ एल्गोरिदम के आधार पर कार्यान्वित किया गया है, लेकिन लेख मुझे समझने के लिए बहुत तकनीकी है)

क्या इसका कोई उलटा कार्य है? वह संख्याओं का अनुक्रम दिया गया है, क्या यह गणितीय रूप से निर्धारित करना संभव होगा कि बीज क्या होगा? (जिसका अर्थ है, ब्रूट-फोर्सिंग वैध विधि के रूप में नहीं गिना जाता है)

[संपादित करें] यहां बहुत सारी टिप्पणियां दिखाई देती हैं ... मैंने सोचा कि मैं जो कुछ ढूंढ रहा हूं उसे स्पष्ट करता हूं ।

तो उदाहरण के लिए, फ़ंक्शन y = f(x) = 3x में एक व्यस्त कार्य है, जो y = g(x) = x/3 है।

लेकिन समारोह z = f(x, y) = x * y एक व्युत्क्रम समारोह क्योंकि (मैं एक पूर्ण गणितीय प्रमाण यहाँ दे सकता है, लेकिन मैं अपने मुख्य प्रश्न गतिरोध नहीं करना चाहती) नहीं है,, सहज शब्दों में, वहाँ (x, y) के एक से अधिक जोड़ी जैसे (x * y) == z।

अब मेरे प्रश्न पर वापस जाएं, यदि आप कहते हैं कि फ़ंक्शन उलटा नहीं है, तो कृपया बताएं क्यों।

(और मैं जो वास्तव में लेख के लिए पढ़ा है उन से उत्तर प्राप्त हो और इसे समझने की उम्मीद कर रहा हूँ। जैसे "यह सिर्फ संभव नहीं है" जवाब वास्तव में मदद नहीं कर रहे हैं)

Answer 1

मैं सामान्य रूप से सिर्फ लेख लिंक नहीं होगा ... लेकिन मुझे एक ऐसी साइट मिली जहां कोई इसे गहराई से देखता था और सोचा था कि यह पोस्टिंग के लायक था। http://jazzy.id.au/default/2010/09/20/cracking_random_number_generators_part_1.html

ऐसा लगता है कि आप एक बीज इस तरह की गणना कर सकते हैं:

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

जहां गुणक २५२१४९०३९१७ है, योज्य 11 है, और परिशुद्धता 48 (बिट) है। आप गणना नहीं कर सकते कि बीज केवल 1 नंबर के साथ क्या था, लेकिन आप 2.

संपादित करें: जैसा कि नहहीद ने कहा कि वहां एक भाग 2 है जहां वह बीज के पीछे गणित में अधिक गुजरता है।

Answer 2

मैं nextInt() द्वारा उत्पन्न पूर्णांक के अनुक्रम को उलट करने के लिए एक कार्यान्वयन प्रस्तुत करना चाहता हूं।

कार्यक्रम nextInt() द्वारा छोड़े गए निचले 16-बिट पर बल को बल देगा, जेम्स रोपर द्वारा ब्लॉग में दिए गए एल्गोरिदम का उपयोग पिछले बीज को खोजने के लिए करें, फिर जांचें कि 48-बिट बीज के ऊपरी 32 बिट समान हैं पिछला नंबर पिछले बीज को प्राप्त करने के लिए हमें कम से कम पूर्णांक की आवश्यकता है। अन्यथा, पिछले बीज के लिए 2 संभावनाएं होंगी, और उनमें से सभी समान रूप से वैध हैं जब तक कि हमारे पास कम से कम एक संख्या न हो।

यह आसानी से nextLong() के लिए बढ़ाया जा सकता है, और long संख्या बीज लगाने के लिए पर्याप्त है, क्योंकि हम एक long, due to the way it is generated में बीज के ऊपरी 32-बिट के 2 टुकड़े हैं।

ध्यान दें कि ऐसे मामले हैं जहां परिणाम SEED चर में गुप्त बीज के रूप में सेट के समान नहीं है।यदि आपके द्वारा गुप्त बीज के रूप में सेट की गई संख्या 48-बिट से अधिक है (जो आंतरिक रूप से यादृच्छिक संख्या उत्पन्न करने के लिए उपयोग की जाने वाली बिट्स की संख्या है), तो के 64 बिट के ऊपरी 16 बिट्स को setSeed() विधि में हटा दिया जाएगा। ऐसे मामलों में, लौटाया गया परिणाम आपके द्वारा शुरू में सेट किए गए जैसा ही नहीं होगा, यह संभावना है कि निचला 48-बिट समान होगा।

मैं जेम्स रोपर, this blog article के लेखक जो नमूना कोड संभव नीचे बना देता है के लिए सबसे अधिक श्रेय देना चाहते हैं:

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

हम ओरेकल (उर्फ़ सूर्य) java.util.Random के कार्यान्वयन के बारे में बात कर रहे हैं , फिर हां, एक बार जब आप पर्याप्त बिट्स जानते हैं तो यह संभव है।

Random 48-बिट बीज और एक रैखिक संगत जनरेटर का उपयोग करता है। ये छोटे राज्य के आकार (ब्रूटफोर्सबल!) की वजह से क्रिप्टोग्राफिक रूप से सुरक्षित जेनरेटर नहीं हैं और तथ्य यह है कि आउटपुट सिर्फ यादृच्छिक नहीं है (कई जनरेटर कुछ बिट्स में छोटी चक्र लंबाई प्रदर्शित करेंगे, जिसका अर्थ है कि उन बिट्स को आसानी से भविष्यवाणी भी की जा सकती है अगर अन्य बिट यादृच्छिक लगते हैं)।

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

यह एक बहुत ही सरल कार्य है, और यह की गणना

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

द्वारा अगर आप बीज के सभी बिट्स पता उल्टे जा सकता है:

Random के बीज अद्यतन इस प्रकार है चूंकि 0x5DEECE66DL * 0xdfe05bcb1365L = 1 मोड 2 । इसके साथ, समय के किसी भी बिंदु पर एक एकल बीज मूल्य को सभी पिछले और भविष्य के बीज को पुनर्प्राप्त करने के लिए पर्याप्त है।

Random में कोई कार्य नहीं है जो पूरे बीज को प्रकट करता है, हालांकि, हमें थोड़ा चालाक होना होगा।

अब, जाहिर है, 48-बिट बीज के साथ, आपको आउटपुट के कम से कम 48 बिट्स का निरीक्षण करना होगा या आपके पास स्पष्ट रूप से इंजेक्शन (और इस तरह उलटा) कार्य नहीं है। हम भाग्य में हैं: nextLong((long)(next(32)) << 32) + next(32); देता है, इसलिए यह आउटपुट के 64 बिट (हमें आवश्यकता से अधिक) उत्पन्न करता है। दरअसल, हम शायद nextDouble (जो 53 बिट्स उत्पन्न करता है) के साथ कर सकते हैं, या किसी भी अन्य फ़ंक्शन की बार-बार कॉल कर सकते हैं। नोट इन कार्यों कर सकते हैं 2 से अधिक उत्पादन नहीं बीज की सीमित आकार की वजह से विशिष्ट मानों कि (इसलिए, उदाहरण के लिए, वहाँ 2 -2 हैं long कि nextLong उत्पादन कभी नहीं होगा)।

चलिए विशेष रूप से nextLong देखें। यह (a << 32) + b पर एक नंबर देता है जहां a और b दोनों 32-बिट मात्राएं हैं। snextLong से पहले बीज बनें। फिर, t = s * 0x5DEECE66DL + 0xBL दें, ताकि at की उच्च 32 बिट्स हो, और u = t * 0x5DEECE66DL + 0xBL दें ताकि bu की उच्च 32 बिट्स हो। c और d क्रमश: t और u की निम्न 16 बिट्स बनें।

ध्यान दें कि c और d 16-बिट मात्राएं हैं, इसलिए हम केवल उन्हें मजबूर कर सकते हैं (क्योंकि हमें केवल एक की आवश्यकता है) और इसके साथ किया जाना चाहिए। यह बहुत सस्ता है, क्योंकि 2 केवल 65536 - कंप्यूटर के लिए छोटा है।लेकिन चलो थोड़ा और चालाक हो और देखें कि क्या कोई तेज तरीका है।

हमारे पास (b << 16) + d = ((a << 16) + c) * 0x5DEECE66DL + 11 है। इस प्रकार, कुछ बीजगणित करते हुए, हम (b << 16) - 11 - (a << 16)*0x5DEECE66DL = c*0x5DEECE66DL - d, मॉड 2 प्राप्त करते हैं। चूंकि c और d दोनों 16-बिट मात्राएं हैं, c*0x5DEECE66DL में अधिकतम 51 बिट्स हैं। यह उपयोगी मतलब यह है कि

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

सबसे 6. पर कुछ k के लिए c*0x5DEECE66DL - d के बराबर है (वहाँ की गणना करने के c और d और अधिक परिष्कृत तरीके हैं, लेकिन क्योंकि k पर बाध्य इतना छोटा है, यह सिर्फ bruteforce आसान है) ।

हम सिर्फ जब तक हम एक मूल्य कौन शेष आधुनिक 0x5DEECE66DL नकार दिया गया, 16 बिट (आधुनिक 2 फिर से) है, ताकि हम t और u दोनों के निचले 16 बिट की वसूली प्राप्त k के लिए सभी संभव मूल्यों का परीक्षण कर सकते हैं। उस समय, हमारे पास एक पूर्ण बीज है, इसलिए हम दूसरे समीकरण का उपयोग करके पहले समीकरण, या पिछले बीज का उपयोग कर भविष्य के बीज पा सकते हैं।

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()); 
    } 
}