เราสามารถรวมเครื่องกำเนิดสุ่มจริงสองตัวเพื่อรับเครื่องใหม่ได้หรือไม่?

เป็นที่ทราบกันดีว่าเครื่องกำเนิดการสุ่มที่แท้จริงใช้ประโยชน์จากการสุ่มที่เกิดขึ้นในปรากฏการณ์ทางกายภาพบางอย่าง นอกจากนี้ เอาต์พุตของตัวสร้างการสุ่มที่แท้จริงสามารถเป็นได้ทั้งแบบเอนเอียงหรือแบบสัมพันธ์กัน ดังนั้นจึงต้องใช้เทคนิคการเอียง

คำถามของฉันคือถ้าเรามีตัวสร้างบิตสุ่มจริงสองตัวที่เอาต์พุตไม่ผ่านชุดการทดสอบของ NIST เราจะรวมเอาต์พุตเหล่านี้เพื่อให้ได้ตัวสร้างบิตสุ่มที่ผ่านชุดการทดสอบการสุ่มเชิงสถิติได้หรือไม่

สิ่งนี้ทำได้ค่อนข้างบ่อยในวงจร พิจารณา TRNG ดิจิตอลทั่วไปทั้งหมดโดยอิงจากออสซิลเลเตอร์แบบวงแหวน:-

ข้างต้นเป็นตัวอย่างที่รุนแรงยิ่งกว่าของคุณ ซึ่งมีการใช้ออสซิลเลเตอร์แบบวงแหวนแต่ละตัวหลายตัว (อาจถึง 32 ตัว) พวกมันเหมือนกันหมด ล้มเหลวในการทดสอบแบบสุ่มอย่างน่าทึ่ง แต่สร้างเอนโทรปีด้วยตัวมันเอง หากต้องใช้ออสซิลเลเตอร์แบบวงแหวน 32 ตัวเพื่อสร้างเอนโทรปี 1 บิต/ขีด คุณสามารถจินตนาการได้ว่าแต่ละตัวจะต้องสร้างค่าน้อยกว่ามาก อคติของพวกเขาจะต้องสูงมากด้วย (ซึ่งเป็นลักษณะของออสซิลเลเตอร์ดังกล่าว) การรวมเข้าด้วยกันจะช่วยเพิ่มอัตราเอนโทรปีได้อย่างมาก และลดอคติเอาต์พุต

อีกตัวอย่างหนึ่งคือรุ่นของ $m \คูณ n$ เมทริกซ์ตัวแยกความสุ่มที่ใช้ใน TRNG จาก ID Quantique เอกสารทางเทคนิคเกี่ยวกับ Randomness Extractor เวอร์ชัน 1.0 กันยายน 2555:-

ตามหลักการแล้ว แหล่งข้อมูลแต่ละรายการที่ใช้ในขั้นตอนที่อธิบายไว้เพื่อสร้างเมทริกซ์ m ควร หาได้จากแหล่งต่างๆ

สิ่งนี้แสดงให้เห็นถึงแนวคิดโดยสังเขปในทางคณิตศาสตร์ กระบวนทัศน์ที่เหมาะสมคือ Piling Up Lemma (Mitsuru Matsui, วิธีเข้ารหัสลับเชิงเส้นสำหรับ DES Cipher) :-

สำหรับ $n$ ตัวแปรไบนารีสุ่มอิสระ $X_1, X_2, \ldots X_n$,

$$ Pr(X_1 \oplus \ldots \oplus X_n = 0) = \frac{1}{2} + 2^{n-1} \prod_{i=1}^n \epsilon_i $$

จัดเรียงใหม่ดังนั้นถ้า $ \epsilon_{1,2, \ldots, n} $ แสดงถึงอคติของ $ X_1 \oplus \ldots \oplus X_n = 0 $เราได้รับอคติสุดท้ายของ $n$ รวมแหล่งข้อมูลอิสระเป็น:-

$$ \epsilon_{1,2, \ldots, n} = 2^{n-1} \prod_{i=1}^n \epsilon_i $$

กล่าวโดยย่อ เมื่อคุณรวม RNG อิสระมากขึ้นเรื่อย ๆ ความเอนเอียงของเอาต์พุตโดยรวมจะมีแนวโน้มเป็นศูนย์โดยไม่แสดงอาการ เลยสร้างใหม่ดีกว่า

ใช่. เราสามารถรวม PRNG สองอันเข้าด้วยกันและสร้างอันที่ดีกว่าได้ รูปแบบที่ง่ายที่สุดคือการ XOR ทั้งสองค่า หากสุ่มอย่างน้อยหนึ่งรายการ ก็จะได้ผลลัพธ์ออกมา สิ่งนี้ไม่ได้แก้ไขทุกอย่าง แต่มีคุณสมบัติที่ดีที่พิสูจน์ได้ โดยพื้นฐานแล้วอย่างน้อยก็ดีพอ ๆ กัน (สมมติว่าไม่มีความสัมพันธ์กันตั้งแต่เริ่มต้น)

อย่างไรก็ตาม หากเรามีแหล่งที่มาที่มีเอนโทรปีจริงบางส่วน เราอาจต้องการใช้แฮชการเข้ารหัส สิ่งนี้ดีแม้กับแหล่ง RNG เดียว

โดยทั่วไปแล้วตัวสร้างแบบสุ่มที่ปลอดภัยจะรวบรวมเอนโทรปีจากแหล่งที่มาที่อ่อนแอหลายแหล่งและผสมพวกมันด้วยการเข้ารหัส (โดยพื้นฐานแล้วคือแฮช) จากนั้นกลุ่มเอนโทรปีนี้เป็นเมล็ดพันธุ์สำหรับ PRNG ที่ปลอดภัยด้วยการเข้ารหัส สมมติว่าเรากังวลเกี่ยวกับศัตรูที่มีการคำนวณที่ไร้ขอบเขต ในกรณีนั้น เราจะพยายามประมาณค่าเอนโทรปีที่แท้จริงที่เรารวบรวมได้ และส่งออกบิตสุ่มจำนวนเล็กน้อยเท่านั้น จนกว่าเราจะรวบรวมเอนโทรปีได้มากขึ้น