ความแข็งแกร่งของการเข้ารหัส RSA มาจากความแข็ง (หรือที่เราเชื่ออย่างนั้น) ของการแยกตัวประกอบจำนวนมาก สำหรับคีย์ที่มีความยาวมากกว่า 2048 บิต เป็นไปไม่ได้ที่คอมพิวเตอร์ปัจจุบันหรืออนาคตอันใกล้จะแยกตัวประกอบของตัวเลขเหล่านั้นในเวลาที่เหมาะสม
แต่สมองของมนุษย์ล่ะ? มีคนที่มีความสามารถทางคณิตศาสตร์ที่น่าทึ่ง ตัวอย่างเช่น นักปราชญ์ที่สามารถคำนวณที่ซับซ้อนได้มากมาย ลองนึกภาพคนที่จดจ่ออยู่กับการแยกตัวประกอบของจำนวน บางทีความสามารถของเขาหรือเธออาจถูกเสริมด้วยยา
นี่เป็นข้อกังวลที่แท้จริงเมื่อออกแบบการเข้ารหัสลับหรือไม่? องค์กรชั่วร้ายสามารถจ้างคนเหล่านี้เพื่อถอดรหัสคีย์การเข้ารหัส (สำหรับรหัสสมัยใหม่) ได้หรือไม่? อาจจะมีบางตัวอย่างในชีวิตจริง?
เครื่องคิดเลขจิต ไม่มีผลลัพธ์ปรากฏในสมองโดยจ้องที่อินพุต พวกเขาทำตามอัลกอริทึม (ลำดับกว้าง ๆ ) บางอย่าง¹ และคอมพิวเตอร์มีประสิทธิภาพเหนือกว่าอย่างมากเมื่อใช้อัลกอริทึมเดียวกัน นั่นคือปัจจัยอย่างน้อย >100 สำหรับคอมพิวเตอร์ส่วนบุคคลราคาไม่แพงในช่วงปลายทศวรรษ 1970
ตัวอย่างเช่น บันทึกการคูณ 10 ของตัวเลข 8 หลักสองตัวจะระบุไว้ที่ 162 วินาที (แหล่งที่มา). แม้ว่าอัลกอริทึมสมุดเรียนจะทำงานเป็นทศนิยม แต่งานที่แย่กว่านั้นต้องใช้การดำเนินการเบื้องต้น 640 รายการที่เกี่ยวข้องกับทศนิยม 4 หลัก หนึ่ง แอปเปิล ][ ด้วยโปรแกรมที่เหมาะสม (แอสเซมบลี 6502) จะทำสิ่งนี้ได้ดีภายใน 1 วินาที รวมถึงการแยกตัวเลขจากและจัดเก็บผลลัพธ์ลงในหน่วยความจำ "ข้อความ" ของหน้าจอ
ฉันสรุปได้ว่าเราสามารถลดราคาอัจฉริยะของมนุษย์ได้โดยสิ้นเชิงเมื่อทำลายคอมพิวเตอร์ เหมาะสม การเข้ารหัสลับ
ปรับปรุง: the ที่มาเดียวกัน ระบุว่าเป็นการบันทึกทางจิตใจใน 6'38" ปัจจัยของคอมโพสิต 5 หลักแบบสุ่ม 20 รายการ ซึ่งง่ายกว่าการหา biprimes RSA ที่เหมาะสมมาก สิ่งนี้กำลังบอกเกี่ยวกับสมองของมนุษย์ไม่เก่งเรื่องการแยกตัวประกอบ
อัปเดต 2: มันยังระบุเป็นประสิทธิภาพแฟคตอริ่งของจำนวนเต็ม 16 (ตอบกลับ 15, 14) หลักที่ทราบกันดีว่าเป็นผลคูณของสี่ ติดต่อกัน จำนวนเฉพาะที่ค่าเฉลี่ย 23'24" (resp. 13'21", 6'06") ฉันเดาว่า Apple ][ สามารถทำได้ดีกว่าด้วยปัจจัย â10000 แม้จะทำงานเป็นทศนิยม โดยใช้ขั้นตอนเดียวของ วิธีการของแฟร์มาต์สำหรับการแยกตัวประกอบทั้งสามตัว
¹ ดู นักแสดงคูณเลข 20 หลักสองตัว ใน 5'26"; สถิติโลกระบุไว้ที่ 2'48"
ความคิดของคุณขัดกับสามัญสำนึกในการเข้ารหัสและการคำนวณ และพูดตรงๆ ก็คือ มันเป็นวิทยาศาสตร์ลวงตาที่โจ่งแจ้ง
สมองของมนุษย์และเซลล์ประสาทภายในทำงานในสถานะสเกลาร์ แม้ว่าจะพิสูจน์ได้ว่ากระบวนการของสมองเป็นแบบกำหนดขึ้นหรือความน่าจะเป็น แต่ก็ไม่มีความสามารถในการสร้างสถานะซ้อนทับอย่างที่คอมพิวเตอร์ควอนตัมทำได้ ดังนั้นจึงไม่มีข้อได้เปรียบเหนือซูเปอร์คอมพิวเตอร์คลาสสิกในเรื่องการแยกตัวประกอบจำนวนเต็มหรือลอการิทึมแยก (อัลกอริทึมของ Shor) และไม่มีประโยชน์ใด ๆ ในการค้นหาผ่านฐานข้อมูลที่ไม่เรียงลำดับ (อัลกอริทึมของ Grover)
สำหรับสมองของมนุษย์ มันง่ายเกินไปที่จะเพิกเฉยต่อความลึกของ 2048+บิต รูป. ลองทำแบบฝึกหัดการคาดเดาทางวิศวกรรมเพื่ออธิบาย
โพสต์ต้นฉบับโดย @derjack มีความยาวเกือบ 700 ตัวอักษร นี่คือตัวเลข 2048 บิต ซึ่งเขียนด้วยทศนิยม 617 หลัก (เกือบเท่ากับคำถาม):
32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448280710318450446268407511633591722075539194702809692695116208601753153385228164358637425253452063124531982403270024154882788029124087013649227429510942494747262878176328960795460204004486651813356499189783184670257748061985168288109350852763136493356212118910302261417784227884243069534873234110239729827362916848850208533176280055919120540762635115410724871087269605319201076899957787049604743491139956908133927452563472712188255099007744935013999050172650250829825
คุณสามารถเข้าใจได้ว่ามันเป็นจำนวนประกอบ (เช่น ไม่ใช่จำนวนเฉพาะ)
คุณยังสามารถดูอย่างใกล้ชิดและสังเกตว่าตัวเลขสุดท้ายคือ 5 ดังนั้น 5 จึงเป็นตัวหาร แต่เป็นความท้าทาย คุณสามารถหาปัจจัยที่ใหญ่กว่าได้หรือไม่?
มาสร้างขอบเขตที่ต่ำกว่าในเวลาที่มนุษย์ที่มีอยู่สามารถถอดรหัสนี้ได้ การอ้างอิงของฉันไม่ชัดเจนที่นี่¹ แต่ดูเหมือนว่าจะเป็นไปได้ 3850 คำต่อนาที เป็นขอบเขตบนของความเร็วในการอ่านของมนุษย์ แปลงแล้วคือ 302 อักขระต่อวินาที (โดยมีความยาวคำเฉลี่ย 4.7 คำในภาษาอังกฤษ²) ฉันจะคาดการณ์ตัวเลขนี้เป็นตัวเลขยาวด้วย ก็มาถึงสนามบอลของ 300 หลักต่อวินาที ความเร็วในการอ่าน
>>> 617 / 301.6
2.045755968169761
เดอะ มนุษย์อ่านเร็วที่สุดในโลก จะต้อง ไม่น้อย กว่า 2,045 มิลลิวินาที เพียงเพื่อโหลดตัวเลขลงในหน่วยความจำ สำหรับผู้อ่านทั่วไปเช่นฉันและคุณ มีตัวประกอบ 17ù; ดังนั้น แค่อ่านตัวเลข จะใช้เวลา 35 วินาทีไม่น้อยสังเกตว่าสำหรับการประมาณค่าขอบเขตล่างที่เราทำอยู่นี้ เราต้องถือว่า ไม่มีที่สิ้นสุด จำนวนเต็ม FLOPS ประสิทธิภาพของสมอง 35 วินาทีจะเป็น IO ก่อนการคำนวณ
¹: https://www.brainread.com/th/the-fastest-reader-in-the-world/
²: https://norvig.com/mayzner.html
ตอนนี้ฉันขอแนะนำให้คุณออกกำลังกายซ้ำเช่น สำหรับ 4096 บิต ยังไม่ถึงสองเท่า! ระดับนามธรรมผิดถ้าคุณคิดอย่างนั้น 4096-bit numbers are on average 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 times larger than 2048-bit numbers, in absolute value.
แบบฝึกหัดนี้อาจช่วยให้คุณรู้ว่าการได้ยินบางอย่างเกี่ยวกับการคำนวณ "N-bits" นั้นง่ายเพียงใดและจินตนาการว่าคุณเข้าใจบางสิ่ง นั่นคือ ทาง ยากกว่าที่คิดถ้าคุณทำคณิตศาสตร์
มนุษย์คนใดก็ตามที่สามารถแยกตัวประกอบตัวเลข 2048 บิตในหัวได้เร็วกว่าคอมพิวเตอร์ เกือบจะแน่นอนว่าเป็นมนุษย์ที่ค้นพบอัลกอริธึมใหม่เพื่อแยกตัวประกอบตัวเลข ซึ่งถ้าใช้งานบนคอมพิวเตอร์ก็จะยิ่งเร็วขึ้นไปอีก
แต่นั่นไม่ได้ควบคุมสิ่งนี้
ฉันจะแม่นยำน้อยกว่าด้านล่างเล็กน้อย ตัวอย่างเช่น ฉันจะผสมปัญหาการตัดสินใจและอัลกอริทึมเพื่อให้เงื่อนไขง่าย
เราไม่รู้ว่าตัวเลขแฟคตอริ่งยากแค่ไหน เรารู้ว่ามันอยู่ในคลาสความซับซ้อน BQP ซึ่งสำหรับคอมพิวเตอร์คลาสสิก (หรือมนุษย์ที่ใช้อัลกอริทึมคลาสสิกในหัว) ใน NP
ปัญหาอยู่ใน NP ถ้าค่อนข้างถูก ตรวจสอบ คุณได้คำตอบที่ถูกต้อง ตัวอย่างในที่นี้คือ ถ้ามีคนระบุว่าตัวประกอบของจำนวนบางตัวคือ A และ B คุณสามารถตรวจสอบได้โดย ... คำนวณ A*B แล้วดูว่าตรงกันหรือไม่
แต่ไม่มีข้อพิสูจน์ว่า NP ไม่เหมือนกับ P ถ้า NP=P ทุกปัญหาสามารถแก้ไขได้ ตรวจสอบแล้ว รวดเร็วได้ แก้ไข เร็ว. (นี่เป็นการโบกมือมาก แต่จริงภายในขอบเขตเหล่านั้น) และถ้า NP=P ดังนั้น BQP ซึ่งอยู่ใน NP ก็จะอยู่ใน P ด้วย
สำหรับปัญหาใน NP เรารู้ว่าไม่มีอัลกอริทึมแบบคลาสสิกใดที่เร็วกว่า "ลองทุกความเป็นไปได้" ที่นี่สำหรับคำจำกัดความที่กว้างขวางของ "ทั้งหมดนั้น" (อัลกอริทึมแฟคตอริ่งที่เร็วที่สุดคือเลขชี้กำลังย่อยอย่างเคร่งครัด เช่น O(e^(k + bits^(1/3)*ln(bits)^(2/3)) ถ้าฉันคัดลอกถูกต้อง)
ดังนั้น หากมีคนคิดอัลกอริทึมเพื่อแยกตัวประกอบจำนวนมากซึ่งเป็นเวลาพหุนาม ในทางทฤษฎีแล้ว พวกเขาสามารถเรียนรู้วิธีเรียกใช้อัลกอริทึมในหัวของพวกเขา และสามารถแยกตัวประกอบจำนวนมากได้เร็วกว่าที่คอมพิวเตอร์ใดๆ จะทำได้
สิ่งนี้ไม่น่าเชื่อ และตามจริงแล้วอัลกอริทึมดังกล่าวน่าจะมีประโยชน์มากกว่าที่จะแบ่งปันในหัวของคุณ
เมธีสามารถหาตัวประกอบได้อย่างรวดเร็ว ปราศจาก แสดง NP=P หรือแม้แต่ BQP=P; ตัวอย่างเช่น อาจเป็นไปได้ว่าการแยกตัวประกอบของจำนวนเฉพาะประเภทเฉพาะที่เราใช้สำหรับการเข้ารหัสนั้นง่ายกว่าปัญหาทั่วไป หรืออาจเป็นเปอร์เซ็นต์ที่มากของจำนวนประกอบนั้นง่ายต่อการแยกตัวประกอบ (แต่ไม่ใช่ทั้งหมด) หรือมี "เคสเข้ามุม" อื่น ๆ ที่ช่วยให้ทำงาน (แม้บางครั้ง) ได้เร็วกว่า "ลองทุกเคส" ผลลัพธ์ดังกล่าวจะทรงพลัง แต่จะไม่ปฏิวัติในระดับของการเขียนซ้ำสิ่งที่เราพิจารณาว่าน่าสนใจทางคณิตศาสตร์ (ซึ่งอัลกอริทึม P ที่มีประสิทธิภาพสำหรับปัญหา NP จะทำโดยสุจริต)
คำตอบอื่น ๆ ได้ชี้ให้เห็นอย่างถูกต้องแล้วว่าสมองของสัตว์นั้นช้าอย่างมากและเกิดข้อผิดพลาดได้ง่ายกว่าคอมพิวเตอร์สมัยใหม่ในงานด้านการคำนวณทั้งหมด ยกเว้นบางประเภทเท่านั้นที่ได้รับประโยชน์อย่างมากจากทักษะการจดจำรูปแบบและการวางแผนเฉพาะที่สมองได้รับการพัฒนาขึ้นมา . เห็นได้ชัดว่า นี่ไม่ได้หมายความว่าสมองของสัตว์ไม่สามารถใช้ประโยชน์ในการเข้ารหัสได้ แท้จริงแล้ว การโจมตีด้วยการเข้ารหัสลับที่ดีที่สุดที่รู้จักกันในปัจจุบันล้วนถูกพบโดยสมองของสัตว์อย่างน้อยบางส่วน อย่างไรก็ตาม สำหรับโครงร่างการเข้ารหัสมาตรฐาน ดูเหมือนว่าไม่น่าจะเป็นไปได้อย่างมากที่สมองจะทำได้ วิ่ง การโจมตีที่ประสบความสำเร็จ (อย่างไรก็ตาม มันอาจจะมีประโยชน์มากในขั้นตอนของ การวางแผน มัน).
ที่กล่าวว่า ฉันพบคำถามที่น่าขบขันว่าสามารถออกแบบรูปแบบการเข้ารหัสที่ปลอดภัยจากการโจมตีที่รู้จักทั้งหมดซึ่งใช้อัลกอริทึมการโจมตีที่ระบุได้อย่างสมบูรณ์ แต่ไม่ปลอดภัยจากการเข้ารหัสด้วยกระดาษและดินสอ ฉันไม่คิดว่าคำตอบนี้เป็นลบอย่างเห็นได้ชัด ตัวอย่างเช่น ลองนึกถึงการเข้ารหัสลำดับบิตสุ่มที่ยาวเป็นชุดของโครงร่าง Winograd จากนั้นเครื่องรับจะแก้ไขโครงร่าง Winograd ด้วยตนเอง และหลังจากนั้นก็ประมวลผลลำดับบิตที่กู้คืนภายหลังเพื่อเพิ่มความเป็นส่วนตัว ขยายความได้เปรียบในการถอดรหัสเทียบกับโมเดลภาษาที่ทันสมัย และรับแผ่นเวลาที่ไม่สามารถสร้างขึ้นใหม่ด้วยความแม่นยำสูงด้วยวิธีอัตโนมัติในที่สุด OTP ที่ได้รับจะถูกใช้เพื่อเข้ารหัสข้อความสั้น
อย่างไรก็ตาม เนื่องจากไม่มีหลักฐานว่าโดยเนื้อแท้แล้วสมองดีกว่าคอมพิวเตอร์ แผนการดังกล่าวทั้งหมดจึงมีแนวโน้มที่จะถูกโจมตีโดยอัตโนมัติในที่สุด
ตัวเลขทศนิยม 617 บิต 2048 บิต @ulidtko ที่โพสต์ด้านบนสามารถแยกตัวประกอบได้ ในไม่กี่ชั่วโมงหรือน้อยกว่านั้น และอาจเป็นไปได้โดยนักปราชญ์ที่มีเครื่องคำนวณจำนวนเต็มขนาดใหญ่ ฉันได้แยกตัวประกอบนี้และพบรูปแบบพิเศษของตัวประกอบ ปัจจัยเล็ก ๆ นั้นง่าย แต่ปัจจัยใหญ่ ๆ นั้นไม่ง่ายหากคุณไม่พบ แบบฟอร์มพิเศษ
ประเภทของความสามารถที่จำเป็นคือความสามารถในการระบุรูปแบบในไบนารี การแสดงตัวประกอบที่เล็กกว่าของจำนวนบิต 2048
ต่อไปนี้คือค่าทศนิยมและเลขฐานสองของตัวประกอบที่ต่ำที่สุด: 3 - 11, 5 - 101, 7 - 111, 13 - 1101, 17 - 10001, 97 - 1100001, 193 - 11000001, 241 - 11110001, 257 - 100000001
คุณเห็นรูปแบบหรือไม่? มี 3 ลาย รูปแบบแรกทั้งหมด 1 ของ 11,111 รูปแบบที่ 2 101,10001, 100000001 ลายที่ 3 อื่นๆ 1101, 1100001, 11110001
รูปแบบที่ 2 คือ 2^k+1 รูปแบบแรกคือ 2^k-1 หากคุณเลือกรูปแบบที่ 2 และทดลองหารปัจจัย 2^k+1 ออก ค่านี้จะลดลง การแยกตัวประกอบ
ปัจจัยคือ: 3^3 x 5^2 x 7 x 13 x 17 x (2^768+1)(2^384+1)(2^256+1)(2^192+1)(2^128+1)(2^96+1)(2^64+1)(2^48+1)(2^32+1)(2^24+1)(2^16+1)(2^12+1)(2^8+1)
หลังจากแบ่งตัวประกอบ 2^k+1 ที่ใหญ่กว่าออก คุณจะเหลือ 1044225=3^3 x 5^2 x 7 x 13 x 17 เพื่อแยกตัวประกอบ
ประวัติ: Alan Turing และแคร็กเครื่อง Enigma ดังนั้น:
นี่เป็นข้อกังวลที่แท้จริงเมื่อออกแบบการเข้ารหัสลับหรือไม่? องค์กรชั่วร้ายสามารถจ้างคนเหล่านี้เพื่อถอดรหัสคีย์การเข้ารหัส (สำหรับรหัสสมัยใหม่) ได้หรือไม่?
ใช่ เท่าที่คุณสามารถค้นหา Alan Turing ของคุณและจัดหาสิ่งที่จำเป็น (หรือสร้างมันใหม่ตั้งแต่ต้น เช่นเดียวกับในกรณีของ "ระเบิด" ของเครื่อง Enigma)
ไม่ ถ้าคุณคิดว่า Alan Turing จะใช้กระดาษและดินสอ
คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา
