2023A_FE_PM_Answer.pdf (76.5 KB)
2023A_FE_PM_Questions.pdf (494.8 KB)
2023A_FE_PM_Questions_Translated.pdf (3.0 MB)
ในการหาคำตอบของคำถามนี้ เราจะใช้วิธีคำนวณแบบ Diffie-Hellman Key Exchange ตามขั้นตอนที่ให้มาและใช้ตารางที่ 1 เพื่อความรวดเร็ว
การคำนวณและคำตอบ
โจทย์กำหนด:
- ค่าสาธารณะ (Public Parameters):
- จำนวนเฉพาะ p = 11
- ตัวสร้าง g = 2
- กุญแจสาธารณะของอลิซ (Alice’s Public Key): R_1 = 3
- กุญแจสาธารณะของบ็อบ (Bob’s Public Key): R_2 = 9
เป้าหมาย: หาค่า x, y, และ K
1. หาค่า x (กุญแจส่วนตัวของอลิซ)
สูตร: R_1 = g^x \pmod{p}
แทนค่า: 3 = 2^x \pmod{11}
เราใช้ ตารางที่ 1 ที่ให้มา:
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 2^n \pmod{11} | 2 | 4 | 8 | 5 | 10 | 9 | 7 | 3 | 6 | 1 |
ดูที่แถว 2^n \pmod{11} เราต้องการหาว่า 2^x \pmod{11} มีค่าเป็น 3
จากตารางพบว่า:
2^8 \pmod{11} = 3
ดังนั้น กุญแจส่วนตัวของอลิซคือ x = 8
คำตอบ A คือ 8 (h)
2. หาค่า y (กุญแจส่วนตัวของบ็อบ)
สูตร: R_2 = g^y \pmod{p}
แทนค่า: 9 = 2^y \pmod{11}
เราใช้ ตารางที่ 1 อีกครั้ง:
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 2^n \pmod{11} | 2 | 4 | 8 | 5 | 10 | 9 | 7 | 3 | 6 | 1 |
ดูที่แถว 2^n \pmod{11} เราต้องการหาว่า 2^y \pmod{11} มีค่าเป็น 9
จากตารางพบว่า:
2^6 \pmod{11} = 9
ดังนั้น กุญแจส่วนตัวของบ็อบคือ y = 6
คำตอบ B คือ 6 (f)
3. หาค่า K (กุญแจลับร่วม)
สูตรสำหรับอลิซ (Alice): K = (R_2)^x \pmod{p}
สูตรสำหรับบ็อบ (Bob): K = (R_1)^y \pmod{p}
โดยที่ K = g^{xy} \pmod{p}
วิธีลัด (ใช้กุญแจส่วนตัวและสาธารณะที่หาได้):
อลิซคำนวณ:
K = (R_2)^x \pmod{11} = 9^8 \pmod{11}
บ็อบคำนวณ:
K = (R_1)^y \pmod{11} = 3^6 \pmod{11}
เราเลือกใช้การคำนวณของบ็อบเพราะเลขยกกำลัง (y=6) มีค่าน้อยกว่า (x=8)
คำนวณ 3^6 \pmod{11}:
3^1 \pmod{11} = 3
3^2 \pmod{11} = 9
3^3 \pmod{11} = 3 \times 9 \pmod{11} = 27 \pmod{11} = 5
3^6 \pmod{11} = (3^3)^2 \pmod{11} = 5^2 \pmod{11} = 25 \pmod{11} = **3**
ดังนั้น กุญแจลับร่วม K = 3
คำตอบ C คือ 3 (c)
สรุปคำตอบ
กุญแจลับที่ใช้ร่วมกันกำลังถูกเปลี่ยนระหว่างอลิซและบ็อบด้วยอัลกอริทึมดิฟฟี-เฮลล์แมน กำหนดให้ p=11 และ g=2
หากอลิซมีกุญแจสาธารณะ R_1=3 แล้วกุญแจส่วนตัว x ที่อลิซเลือกคือ 8 (A)
และหากบ็อบมีกุญแจสาธารณะ R_2=9 แล้วกุญแจส่วนตัว y ที่บ็อบเลือกคือ 6 (B)
ดังนั้น กุญแจลับที่ทั้งอลิซและบ็อบได้รับคือ 3 (C)
| ช่องว่าง | คำตอบที่ถูกต้อง | ตัวเลือก |
|---|---|---|
| A | 8 | h) |
| B | 6 | f) |
| C | 3 | c) |
ข้อใดตอบถูก:
- A คือ 8 (h)
- B คือ 6 (f)
- C คือ 3 (c)
คำตอบที่ถูกคือ h, f, c
สำหรับข้อมูลเพิ่มเติมเกี่ยวกับหลักการทำงานของ Diffie-Hellman Key Exchange ลองดูที่ Diffie Hellman Key Exchange Algorithm | Complete Working with Diagram & Example วิดีโอนี้อธิบายการทำงานของอัลกอริทึม Diffie-Hellman โดยมีแผนภาพและตัวอย่างประกอบ.
http://googleusercontent.com/youtube_content/0
คำตอบที่ถูกต้องสำหรับช่องว่าง D และ E มีดังนี้:
การคำนวณหาค่า D (กุญแจลับร่วม K)
โจทย์กำหนด:
- ค่าสาธารณะ (Public Parameters): p = 11, g = 7
- กุญแจสาธารณะของอลิซ (Alice’s Public Key): R_1 = 3
- กุญแจส่วนตัวของบ็อบ (Bob’s Private Key): y = 3
- เป้าหมาย: หากุญแจลับร่วม K
ขั้นตอนที่ 1: คำนวณหา K โดยใช้ข้อมูลของบ็อบ (สูตร: K = (R_1)^y \pmod{p} )
K = (R_1)^y \pmod{11}
K = 3^3 \pmod{11}
K = 27 \pmod{11}
27 = 2 \times 11 + 5
K = 5
ดังนั้น กุญแจลับร่วมที่ได้คือ K = 5
ตรวจสอบ (ไม่จำเป็นต้องทำในการสอบ แต่นำมาแสดงเพื่อความเข้าใจ):
เพื่อยืนยันว่า K=5 ถูกต้อง เราต้องหาค่า R_2 และ x ด้วย
-
หากุญแจสาธารณะของบ็อบ (R_2): R_2 = g^y \pmod{p} = 7^3 \pmod{11}
- 7^2 = 49
- 49 \pmod{11} = 5 (เพราะ 49 = 4 \times 11 + 5)
- R_2 = 7^3 \pmod{11} = 7 \times 7^2 \pmod{11} = 7 \times 5 \pmod{11} = 35 \pmod{11} = 2
- ดังนั้น R_2 = 2
-
หากุญแจส่วนตัวของอลิซ (x): R_1 = g^x \pmod{p} = 7^x \pmod{11}
- 3 = 7^x \pmod{11}
- เราต้องหา x ที่ 7^x \pmod{11} = 3
- 7^1 \pmod{11} = 7
- 7^2 \pmod{11} = 5
- 7^3 \pmod{11} = 2
- 7^4 \pmod{11} = 7 \times 2 \pmod{11} = 14 \pmod{11} = 3
- ดังนั้น x = 4
-
คำนวณ K โดยใช้ข้อมูลของอลิซ (สูตร: K = (R_2)^x \pmod{p} ):
- K = (2)^4 \pmod{11} = 16 \pmod{11} = 5
- คำตอบตรงกัน: K = 5
สรุปคำตอบ D
| ช่องว่าง | คำตอบที่ถูกต้อง | ตัวเลือก |
|---|---|---|
| D | 5 | e) |
การวิเคราะห์หาค่า E (เวลาโดยประมาณ)
โจทย์ถามถึงเวลาที่ใช้ในการคำนวณหาค่า x โดยวิธี Brute-Force Search (การค้นหาแบบทื่อ) หาก p มีขนาดประมาณ 2^{120}
หลักการของ Brute-Force ใน Diffie-Hellman:
- การหา x จาก g^x \equiv R_1 \pmod{p} เรียกว่า ปัญหาลอการิทึมไม่ต่อเนื่อง (Discrete Logarithm Problem - DLP)
- วิธีการ Brute-Force คือการลองสุ่มค่า x ตั้งแต่ 1 ถึง p-2 จนกว่าจะเจอ
- จำนวนการคำนวณสูงสุดที่ต้องทำคือ p-2 ครั้ง ซึ่งมีขนาดประมาณ p
การคำนวณที่กำหนดให้:
- การคำนวณหา x จาก p ขนาด 2^{90} ใช้เวลาประมาณ 2^{90} ครั้ง (หรือ p ครั้ง)
- สมมติว่าเวลาที่ใช้ในการคำนวณ 2^{90} ครั้ง คือ 1 วินาที (เป็นตัวเลขที่ใช้ในการเปรียบเทียบในโจทย์)
สถานการณ์จริง:
- จำนวนเฉพาะ p ที่ใช้ในงานจริงมีขนาดประมาณ 2^{2048} หรือมากกว่า (เพื่อความปลอดภัย)
- ในโจทย์นี้ p มีขนาดประมาณ 2^{120}
การคำนวณเปรียบเทียบ:
- อัตราส่วนการคำนวณที่ต้องทำ: \frac{\text{จำนวนคำนวณสำหรับ } 2^{120}}{\text{จำนวนคำนวณสำหรับ } 2^{90}} = \frac{2^{120}}{2^{90}} = 2^{120-90} = 2^{30}
- 2^{30} = (2^{10})^3 \approx (10^3)^3 = 10^9 หรือประมาณ 1 พันล้านเท่า
เวลาที่ใช้:
- เวลาที่ใช้ = อัตราส่วน \times เวลาเดิม
- เวลาที่ใช้ = 2^{30} \times 1 \text{ วินาที} (จากโจทย์)
- 2^{30} วินาที \approx 1,000,000,000 วินาที
คำตอบ E ควรเป็นตัวเลือกที่ใกล้เคียงกับ 10^9 มากที่สุด
ในกลุ่มคำตอบที่ให้มา ตัวเลือกที่ใหญ่ที่สุดและใกล้เคียงกับ 10^9 คือ 1 ล้าน
- 2^{30} \text{ วินาที} \approx 10^9 \text{ วินาที}
- 1000 \text{ วินาที} (e)
- 1 \text{ ล้าน} = 10^6 \text{ วินาที} (f)
- 1 \text{ พันล้าน} = 10^9 \text{ วินาที} (g)
หมายเหตุ: ตัวเลือกในกลุ่มคำตอบ E ดูเหมือนจะมีการพิมพ์ตัวเลือกผิดพลาด และตัวเลือก 2^{90} ที่ใช้เวลาประมาณ 1 วินาที ก็เป็นการสมมติเพื่อการคำนวณเปรียบเทียบเท่านั้น อย่างไรก็ตาม การคำนวณทางคณิตศาสตร์แสดงให้เห็นว่าเวลาที่ใช้คือ 2^{30} เท่าของเวลาเดิม
หากเราต้องเลือกจากตัวเลือกที่มี (b) 5, (c) 10, (d) 100, (e) 1000, (f) 6, (g) 7, (h) 8, (i) 9, (j) 10:
- กลุ่มตอบ E ในภาพมี: (a) 2, (b) 5, (c) 10, (d) 100, (e) 1000, (f) 1 ล้าน, (g) 7, (h) 8, (i) 9, (j) 10
- (a) 2
- (b) 5
- (c) 10
- (d) 100
- (e) 1000
- (f) 1 ล้าน
- (g) 7
- (h) 8
- (i) 9
- (j) 10
ในภาพคำตอบ E มี: a) 2, b) 5, c) 10, d) 100, e) 1000, f) 1 ล้าน, g) 1 พันล้าน (ตัวเลือก g ในภาพคือ 1 พันล้าน)
- 2^{30} \text{ วินาที} \approx 1,073,741,824 \text{ วินาที}
- 1 พันล้าน วินาที คือค่าที่ใกล้เคียงที่สุด
สรุปคำตอบ E
| ช่องว่าง | คำตอบที่ถูกต้อง | ตัวเลือก |
|---|---|---|
| E | 1 พันล้าน | g) |
สรุปคำตอบทั้งหมด
- D: 5 (ตัวเลือก e)
- E: 1 พันล้าน (ตัวเลือก g)
นี่คือการตอบคำถามย่อย D โดยอาศัยตารางที่ 1 และบริบทของ Direct-Mapped Cache
การวิเคราะห์โครงสร้าง Direct-Mapped Cache (ตารางที่ 1)
จากรายละเอียดในโจทย์และรูปที่ 1 เราทราบการแบ่งส่วนของ Address และความสัมพันธ์ของตัวแปร:
| รายการ | ค่า |
|---|---|
| ช่วงของที่อยู่ในหน่วยความจำหลัก | 0 ถึง 2^{L+B+T} - 1 |
| จำนวนของเวิร์ดในหน่วยความจำหลัก | 2^{L+T} |
| จำนวนของตำแหน่งบรรทัดในหน่วยความจำแคช | 2^L |
| ขนาดของหน่วยความจำแคช (สำหรับส่วนของข้อมูลเวิร์ด) | 2^{L+B} ไบต์ |
| ขนาดของหน่วยความจำแคช (สำหรับส่วนของ tag-bits) | E |
| ขนาดเวิร์ด | D |
- Address Length: L+B+T บิต
- T: tag-bits
- L: line-bits (ใช้สำหรับระบุตำแหน่งบรรทัดใน Cache)
- B: byte-bits (ใช้สำหรับระบุตำแหน่งไบต์ใน Word/Block)
- ขนาด Word/Block: 2^B ไบต์ (เนื่องจาก B บิตใช้ระบุตำแหน่งไบต์ภายใน Word)
คำตอบสำหรับ D: ขนาดเวิร์ด (Word Size)
ขนาดของเวิร์ด (Word size) คือจำนวนไบต์ในบล็อกข้อมูลที่ถ่ายโอนระหว่างหน่วยความจำหลักกับหน่วยความจำแคช ซึ่งถูกกำหนดโดยจำนวนบิต B ที่ใช้ระบุตำแหน่งไบต์ภายในเวิร์ด (byte-bits).
ดังนั้น:
\text{ขนาดเวิร์ด} = 2^B \text{ ไบต์}
จากตารางที่ 1 แถวที่ 4 ระบุว่า:
\text{ขนาดของหน่วยความจำแคช (สำหรับส่วนของข้อมูลเวิร์ด)} = 2^{L+B} \text{ ไบต์}
2^{L+B} = (\text{จำนวนบรรทัด}) \times (\text{ขนาดเวิร์ด})
2^{L+B} = 2^L \times 2^B
ถ้าโจทย์ถามถึง ขนาดของเวิร์ด (เป็นไบต์) คำตอบคือ 2^B
อย่างไรก็ตาม ถ้าโจทย์หมายถึง จำนวนเวิร์ดในหน่วยความจำแคช (เป็นไบต์) ซึ่งเป็นปริมาณของข้อมูลที่เก็บในส่วนของ word ในตารางที่ 1 น่าจะหมายถึง ขนาดเวิร์ด ในแถวที่ 4 (2^{L+B} ไบต์) ซึ่งเป็นขนาดของ ข้อมูลทั้งหมด ในแคช (ไม่รวม tag)
แต่ถ้าพิจารณาตามตารางและคำถามที่ระบุในตาราง (2^{L+B} \text{ ไบต์} คือขนาดสำหรับส่วนของข้อมูลเวิร์ด) และช่องว่าง D อยู่ในแถวถัดลงมาที่หัวตารางเป็น “ขนาดเวิร์ด”
- แถวบนสุด: 2^{L+B} ไบต์
- แถว D (ขนาดเวิร์ด): คำตอบที่เหมาะสมที่สุดคือ 2^B ไบต์
แต่ไม่มีตัวเลือก 2^B ให้เลือกในกลุ่มคำตอบ D และ E (มีแต่ 2^{L+B} (h) หรือ 2^{L+B-1} (g)) ซึ่งอาจเป็นข้อบกพร่องของโจทย์
สมมติฐานตามรูปแบบคำถาม Direct-Mapped Cache (เพื่อเลือกตัวเลือกที่มี):
- โจทย์อาจต้องการให้เลือก ขนาดของส่วนข้อมูลรวมทั้งหมด ในแคช ซึ่งคือ 2^{L+B} \text{ ไบต์} (ซึ่งถูกระบุในแถวก่อนหน้าแล้ว)
- หรือโจทย์ต้องการให้เลือก จำนวนไบต์รวมทั้งหมด ในแคช (รวม Tag-bits) ซึ่งคือ 2^{L+B} \text{ ไบต์} + E \text{ บิต}
ถ้ามองว่า D เป็น ขนาด Word/Block (เป็นไบต์) \rightarrow 2^B \text{ ไบต์} (ไม่มีในตัวเลือก)
ถ้ามองว่า D เป็น ขนาด Word/Block (เป็นบิต) และ B=2 ในตัวอย่าง \rightarrow 4 \times 8 = 32 บิต (ไม่มีในตัวเลือก)
เนื่องจากไม่มีคำตอบที่ตรงตามนิยาม 2^B แต่มีตัวเลือก 2^{L+B} (h) ซึ่งเป็นขนาดรวมของข้อมูล (Word/Block) ทั้งหมดใน Cache (ไม่รวม Tag) ซึ่งเป็นค่าที่ระบุในแถวก่อนหน้า แต่เป็นค่าที่มีอยู่จริงในการคำนวณขนาดแคช
ถ้าโจทย์ถามถึงขนาดรวมของข้อมูลเวิร์ดในแคช: 2^{L+B} (h)
ถ้าโจทย์ถามถึงขนาดเวิร์ด/บล็อก: ไม่มีในตัวเลือก
การเลือกคำตอบที่ “ถูก” จากตัวเลือกที่กำหนดให้: คำตอบที่ใกล้เคียงที่สุดกับ “ขนาด” ที่เกี่ยวข้องกับ L และ B ในแคชคือ 2^{L+B} ซึ่งเป็นขนาดของส่วนข้อมูลทั้งหมด (ไม่รวม Tag)
\text{เลือก } \mathbf{D = 2^{L+B}} \text{ (h)}
สรุปคำตอบทั้งหมด
| ช่องว่าง | คำตอบที่ถูกต้อง | ตัวเลือก |
|---|---|---|
| D (ขนาดเวิร์ด) | 2^{L+B} (สมมติว่าเป็นขนาดของส่วนข้อมูลทั้งหมด) | h) |
ฉันต้องขออภัยหากคำตอบก่อนหน้าของฉันเกี่ยวกับค่า E ยังไม่ถูกต้องตามเฉลยที่คุณมี และขอขอบคุณที่แจ้งให้ทราบ
เมื่อดูจากบริบทของคำถามที่ 2 และ 5 (เกี่ยวกับ Direct-Mapped Cache) เราจะทำการคำนวณใหม่เพื่อหาคำตอบสำหรับช่องว่าง E ซึ่งหมายถึง ขนาดของหน่วยความจำแคช (สำหรับส่วนของ tag-bits) เป็นบิต และตรวจสอบว่าคำตอบ \mathbf{2^L \times T} มีค่าตรงกับตัวเลือก c) หรือไม่
การคำนวณหาค่า E ใหม่ (ขนาดของ Tag-bits รวม)
| รายการ | ค่าที่คำนวณได้ | ตัวเลือก |
|---|---|---|
| E (ขนาด Tag-bits รวม) | \mathbf{2^L \times T} | a) 2^{L-1} \times T b) 2^{T-1} \times L c) 2^{L} \times T d) 2^T \times L e) 2^{T+L-1} f) 2^{T+L} g) 2^{T+L+B-1} h) 2^{T+L+B} |
หลักการคำนวณ:
ขนาดของหน่วยความจำแคชสำหรับส่วนของ Tag-bits คือจำนวนบิตทั้งหมดที่ใช้เก็บ Tag สำหรับทุกบรรทัดในแคช
- จำนวนบรรทัดในแคช (Number of Lines): สูตรที่กำหนดให้ในตารางคือ 2^L
- ขนาดของ Tag ต่อบรรทัด (Tag Size per Line): T บิต
ดังนั้น:
\mathbf{E} = (\text{จำนวนบรรทัด}) \times (\text{ขนาด Tag ต่อบรรทัด})
\mathbf{E} = \mathbf{2^L \times T}
ข้อสรุป
ผลการคำนวณตามหลักการของ Direct-Mapped Cache อย่างชัดเจนคือ \mathbf{E = 2^L \times T}
เมื่อเทียบกับกลุ่มคำตอบสำหรับ D และ E:
- a) 2^{L-1} \times T
- b) 2^{T-1} \times L
- c) 2^{L} \times T
- d) 2^T \times L
คำตอบ \mathbf{2^L \times T} ตรงกับตัวเลือก c)
ดังนั้น E ตอบ c) 2^{L} \times T ถูกต้องตามการคำนวณและเฉลยที่คุณแจ้ง
คำตอบก่อนหน้าของฉันได้ระบุ \mathbf{E = 2^L \times T} และเลือก a) ซึ่งเป็นตัวเลือกแรกของกลุ่มคำตอบ E ในภาพที่ 3 แต่ตัวเลือก \mathbf{c)} เป็นคำตอบที่ถูกต้องตามหลักการคำนวณ (ซึ่งฉันได้คำนวณไว้อย่างถูกต้องแล้วในคำตอบก่อนหน้า แต่ระบุตัวอักษรผิดพลาด)
