ตัวสร้างเลขสุ่มเทียมแบบบลัมบลัมชับ

ตัวสร้างเลขสุ่มเทียมแบบบลัมบลัมชับ (อังกฤษ : Blum Blum Shub) เป็นตัวสร้างเลขสุ่มเทียมที่ถูกสร้างขึ้นในปี 1986 โดย Lenore Blum, Manuel Blum และ Michael Shub โดยมีเป้าหมายในการใช้ในด้านความปลอดภัยมากกว่าที่จะเอาไปใช้สุ่มตัวเลขจริงๆ

รายละเอียด

โดยตัวสร้างเลขสุ่มเทียมแบบบลัมบลัมชับมีลำดับเป็น

${\displaystyle x_{n+1}=x_{n}^{2}{\bmod {M}}}$ 

มีผลลัพธ์เป็นบิตที่มีความสำคัญน้อยที่สุด(LSB) ของ ${\displaystyle x_{n+1}}$  โดย M=pq โดย p และ q เป็นจำนวนเฉพาะขนาดใหญ่ไม่ซ้ำกัน และทั้งคู่จะสมภาคกับ 3 ภายใต้มอดูโล 4

ลักษณะเฉพาะที่น่าสนใจของตัวสร้างเลขสุ่มเทียมแบบบลัมบลัมชับคือสามารถทีจะคำนวณหาค่า ${\displaystyle x_{i}}$  ใดๆได้โดยตรง(ผ่านทฤษฎีบทของออยเลอร์)

${\displaystyle x_{i}=\left(x_{0}^{2^{i}{\bmod {\lambda }}(M)}\right){\bmod {M}}}$ 

โดย ${\displaystyle \lambda }$  มาจาก Carmichael function (ตามสมการ ${\displaystyle \lambda (M)=\lambda (p\cdot q)=\operatorname {lcm} (p-1,q-1)}$ )

ด้านความปลอดภัย

ตัวสร้างเลขสุ่มนี้ไม่ได้เหมาะกับการนำมาใช้สุ่มค่ามาใช้แต่มีไว้ใช้เฉพาะเพื่อการเข้ารหัส(วิทยาการเข้ารหัสลับ) เพราะทำได้ค่อนข้างช้า อย่างไรก็ตามก็ยังมีวิธีที่จะลดรูปความซับซ้อนในรูปแบบการคำนวณไปเป็นความซับซ้อนในรูปแบบการคำนวณของปัญหา Quadratic residuosity problem เพื่อที่จะแก้รหัสนี้จำเป็นต้องรู้ตัวประกอบของค่าโมดูลัส ความยากในการถอดรหัสตัวประกอบจำนวนเต็มนั้นถือเป็นความปลอดภัยอย่างหนึ่ง เนื่องจากความยากในการถอดรหัสนั้นเองตัวสร้างเลขสุ่มเทียมแบบบลัมบลัมชับที่ใช้ M ขนาดใหญ่นั้นจะมีค่าออกมาแตกต่างกับค่าสุ่มอื่นๆ ที่สามารถแก้ปัญหาด้วยการคำนวณต่างๆ ตัวสร้างเลขสุ่มเทียมแบบบลัมบลัมชับจึงถูกนำไปใช้ในด้านการออกแบบด้านความปลอดภัย โดยมีระบบความปลอดภัยเป็นปัญหาการแยกตัวประกอบเช่นเดียวกับการเข้ารหัสแบบ RSA

ตัวอย่าง

ให้ M = 11*19 = 209 ค่า ${\displaystyle x_{0}}$ = 9 จะได้

• ${\displaystyle x_{1}=9^{2}}$  mod 209 = 81
• ${\displaystyle x_{2}=81^{2}}$  mod 209 = 82
• ${\displaystyle x_{3}=82^{2}}$  mod 209 = 36
• ${\displaystyle x_{4}=36^{2}}$  mod 209 = 42
• ${\displaystyle x_{5}=42^{2}}$  mod 209 = 92
• ${\displaystyle x_{6}=92^{2}}$  mod 209 = 104
• ${\displaystyle x_{7}=104^{2}}$  mod 209 = 157
• ${\displaystyle x_{8}=157^{2}}$  mod 209 = 196
• ${\displaystyle x_{9}=196^{2}}$  mod 209 = 169
• ${\displaystyle x_{10}=169^{2}}$  mod 209 = 137
• ${\displaystyle x_{11}=137^{2}}$  mod 209 = 168
• ${\displaystyle x_{12}=168^{2}}$  mod 209 = 9

อ้างอิง

• Lenore Blum, Manuel Blum, and Michael Shub. "A Simple Unpredictable Pseudo-Random Number Generator", SIAM Journal on Computing, volume 15, pages 364-383, May 1986.
• Lenore Blum, Manuel Blum, and Michael Shub. "Comparison of two pseudo-random number generators", Advances in Cryptology: Proceedings of Crypto '82. Available as Google book.
• Martin Geisler, Mikkel Krøigård, and Andreas Danielsen. "About Random Bits", December 2004. Available as PDF and Gzipped Postscript.

ลิ้งภายนอก

• http://neohumanism.org/b/bl/blum_blum_shub.html
• https://www.cs.indiana.edu/~kapadia/project2/node11.html
• http://www.powerbasic.com/support/pbforums/showthread.php?t=19206