ข้ามไปเนื้อหา

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

จากวิกิพีเดีย สารานุกรมเสรี

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

รายละเอียด

[แก้]

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

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

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

โดย มาจาก Carmichael function (ตามสมการ )

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

[แก้]

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

ตัวอย่าง

[แก้]

ให้ M = 11*19 = 209 ค่า = 9 จะได้

  • mod 209 = 81
  • mod 209 = 82
  • mod 209 = 36
  • mod 209 = 42
  • mod 209 = 92
  • mod 209 = 104
  • mod 209 = 157
  • mod 209 = 196
  • mod 209 = 169
  • mod 209 = 137
  • mod 209 = 168
  • mod 209 = 9

อ้างอิง

[แก้]

ลิ้งภายนอก

[แก้]