Tags:
Node Thumbnail

ฟังก์ชั่นสร้างเลขสุ่มเทียม RC4 ถูกสร้างขึ้นมาเป็นสินค้าตัวแรกๆ ของบริษัท RSA ตั้งแต่ 25 ปีที่แล้ว (เป็นความลับทางการค้าแต่ถูกเปิดเผยอัลกอริทึมภายหลัง) ทุกวันนี้ยังถูกใช้งานจำนวนมากเพราะความง่ายในการอิมพลีเมนต์และความเร็วในการทำงาน แต่ขณะเดียวกับ RC4 ก็มีความอ่อนแอที่รู้กันหลายจุด เช่น ค่าที่สร้างออกมามีความโน้มเอียงตามค่ากุญแจเริ่มต้น, หากใครรู้ค่าสถานะภายในของอัลกอริทึมก็อาจจะกู้คืนกุญแจกลับมาได้, และสามารถสังเกตได้ว่าเอาท์พุตไม่ใช่ค่าสุ่มหากสังเกตตัวอย่างจำนวน 2^41 ตัวอย่าง

Ron Rivest ผู้สร้าง RC4 ร่วมกับ Jacob Schuldt จากมหาวิทยาลัยลอนดอนเสนอฟังก์ชั่น Spritz ฟังก์ชั่นที่ทำงานรูปแบบเดียวกับ RC4 แต่แก้ปัญหาหลายอย่าง นับตั้งแต่ความโน้มเอียงของค่าเอาท์พุตที่หายไป, การสังเกตว่าเอาท์พุตไม่ใช่ค่าสุ่มทำได้ยากขึ้นโดยต้องสังเกตค่าตัวอย่าง 2^81 ตัวอย่าง ขณะเดียวกันก็รักษาคุณสมบัติของ RC4 เช่นการใช้ตัวแปรไม่มากนัก

ฟังก์ชั่นนี้ออกแบบหลังงาน Crypto2013 และนำเสนอเป็นช่วงสั้นๆ (rump session) ในงาน Crypto2014 ทาง Ron Rivest นำเสนอเพื่อชวนให้ผู้สนใจช่วยกันทดสอบความแข็งแกร่งของฟังก์ชั่นนี้

ที่มา - Spritz—a spongy RC4-like stream cipher and hash function (PDF/Slide), รายงานเต็ม (PDF)

Get latest news from Blognone

Comments

By: panurat2000
ContributorSymbianUbuntuIn Love
on 2 September 2014 - 14:36 #737161
panurat2000's picture

ทุกวันนี้มียังถูกใช้งานจำนวนมากเพราะความง่ายในการอิมพลีเมนต์

มียัง ?

หากใครรู้ค่าสถานะภายในของอัลกอริทีมก็อาจจะกู้คืนกุญแจกลับมาได้

อัลกอริทีม => อัลกอริทึม

การสังเกตว่าเอาท์พุตไม่ใช่ค่าสุ่มทำไ้ดยากขึ้น

ทำไ้ด => ทำได้

โดยต้องสังเกตุค่าตัวอย่าง 2^81 ตัวอย่าง

สังเกตุ => สังเกต

ทาง Ron Rivest นำเสนอเื่พอชวนให้ผู้สนใจช่วยกันทดสอบ

นำเสนอเื่พอ => นำเสนอเพื่อ

By: ApiratN on 2 September 2014 - 15:36 #737193
ApiratN's picture

ถามหน่อยครับ
อ่านใน wiki ไม่เข้าใจ
ทำไมต้องสุ่มเลขเทียม?
สร้างสุ่มเทียมก่อนสุ่มจริง? สุ่มไปเฉยๆ เลยไม่ได้เหรอครับ

แล้วทำไมต้องมีบริษัทขายฟังก์ชั่นสุ่ม ในเมื่อใช้พวกโปรแกรมมันก็มีฟังก์ชั่นสุ่มให้อยู่แล้ว เช่น rand() เค้าขายให้ใครครับ

By: SomeThing
Windows
on 2 September 2014 - 17:01 #737222 Reply to:737193

ช่วยตอบครับ ตามความเข้าใจผมนะครับ

เลขสุ่มจริงในทางคอมพิวเตอร์ไม่มีหรอกครับ อย่าง rand() ที่ยกตัวอย่างมา ก่อนจะใช้เราก็ต้องใช้ srand เพือกำหนดค่าเริ่มต้น(seed)ก่อนใช่มั๊ยครับ ซึ่งมันมักจะเป็นค่าเวลาของเครื่องคอมพิวเตอร์ เช่น srand (time(NULL));

คราวนี้เลขสุ่มที่สร้างจากฟังชั่น rand() ค่าที่ได้ก็เกิดจากการเอาค่า seed เริ่มต้นมาปู้ยี่ปู้ยำตามอัลกอริทึมที่อยู่ใน rand()และเนื่องจากอัลกอริทึมมันคงที่ถ้าเรารู้ค่า seed เริ่มต้นเราก็สามารถระบุค่าปลายทางได้ แบบนี้แหละครับที่เค้าเรียกการสุ่มเทียมเพราะค่าที่ได้มันสามารถทำนายได้ ถ้าเรารู้ข้อมูล seed ต้นทาง

ในการพัฒนาการสร้างเลขสุ่มจึงเน้นไปที่การหาค่า seed เริ่มต้นที่เดาได้ยากจริงๆ อย่างเช่นค่าจากเซนเซอร์ที่วัดอุณหภูมิ CPU อะไรประมาณนี้

แนะนำให้อ่านบทความนี้ประกอบครับ https://www.blognone.com/node/43969

By: ApiratN on 3 September 2014 - 12:48 #737486 Reply to:737222
ApiratN's picture

ขอบคุณมากๆ ครับ

By: lew
FounderJusci's WriterMEconomicsAndroid
on 2 September 2014 - 17:36 #737236 Reply to:737193
lew's picture

สั้นๆ:

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

ยาวๆ: อ่าน Random Generator


lewcpe.com, @wasonliw

By: sukoom2001
ContributorAndroidUbuntu
on 2 September 2014 - 18:16 #737243
sukoom2001's picture

ค่าสุ่มที่ได้จากคอมไพเลอร์ มัก ถูกเขียนมาด้วย algorithm ที่ไม่ซับซ้อน และเน้นความเร็วและง่ายเป็นหลักอย่างพวก
Linear Congruential

ซึ่งมีปัญหาหลายประการครับ ที่เห็นภาพชัดเจนที่สุดคือ รูปนี้ครับ

alt="Hyperplane"

คือ algorithm นี้ ไม่สามารถ สุ่มค่า ให้แต่ละจุด บน hyperplane ด้วยความน่าจะเป็นที่เท่ากันครับ

ถ้านำไปใช้กับงานด้าน simulation บางอย่าง จะทำให้ได้ค่าที่ bias ผิดพลาดจากที่ควรครับ

By: ApiratN on 3 September 2014 - 12:48 #737488 Reply to:737243
ApiratN's picture

ขอบคุณครับ