ฉันกำลังพยายามทำความเข้าใจ "ของมิตสึรุ มัตสึอิ"วิธีเข้ารหัสลับเชิงเส้นสำหรับ DES Cipher" โดยเฉพาะการโจมตีที่เขาอธิบายไว้ตอนท้ายของหัวข้อที่ 5 ใน DES 5 รอบ ฉันติดตามการโจมตีถึง 3 รอบ และนี่คือคณิตศาสตร์สำหรับมัน:
สำหรับ DES 5 รอบ ฉันกลั่นสิ่งต่างๆ เพื่อให้มีตัวแปรเพียง 4 ประเภท:
เนื่องจากทุกตัวแปรเป็นอย่างใดอย่างหนึ่งหรือ XOR ของสองอย่าง Matsui กล่าวว่าควรใช้สมการสีแดงในรอบที่ 1 และ 5 และสมการสีเขียวในรอบที่ 2 และ 4 การตั้งค่าจะเป็นดังนี้:
คำถามของฉันคือ:
ขอบคุณ!
แก้ไข: ฉันสามารถพิสูจน์การประมาณ 5 รอบได้ แต่จริงๆ แล้วฉันไม่เข้าใจสิ่งที่ฉันทำ ฉันแค่ทำตามสมการและตัวแปรบางตัวก็หายไป:
ฉันชอบที่จะเข้าใจวิธีการทำงานโดยทั่วไป ในตารางของ Matsui ในตอนท้าย เขาใช้เส้นทางการประมาณเช่น "AB-BA" สิ่งนี้หมายถึงอะไรอย่างเป็นทางการ และเหตุใด A และ B จึงเชื่อมกันได้ทั้งสองแบบ
พบคำตอบ
ก่อนอื่น ฉันจะเปลี่ยนสัญลักษณ์เล็กน้อยเพื่อให้สมการมีความสมมาตรมากขึ้น
การใช้สัญกรณ์นี้ คำที่เป็นข้อความธรรมดา $PH$ ในกระดาษของมัตสึอิกลายเป็น $x_0$, และ $PL$ กลายเป็น $x_1$. คำไซเฟอร์เท็กซ์ $CH$ กลายเป็น $x_{n+1}$, และ $CL$ กลายเป็น $x_n$.
เราสามารถหาค่าประมาณของ $n$ รอบผ่านการค้นหากราฟ โหนดในกราฟนี้จะมีลักษณะดังนี้:
$$ \bigoplus_{i=0}^{n+1} x_i[\delta_i] = \bigoplus_{i=1}^n k_i[\epsilon_i] \tag{1} $$
ที่ไหน $\delta_i$ และ $\epsilon_i$ เป็นบิตมาสก์
หากต้องการดูว่าขอบเป็นอย่างไร สมมติว่าเรามี 1 รอบโดยประมาณดังนี้:
$$ x[\alpha] \oplus F(x, k)[\beta] = k[\gamma] \tag{2} $$
เราสามารถยกตัวอย่างเป็นรอบได้ว่า $i$เพื่อรับ:
$$ x_i[\alpha] \oplus F(x_i, k_i)[\beta] = k_i[\gamma] \tag{3} $$
และตอนนี้เราสามารถใช้โครงสร้าง Feistel ได้แล้ว $x_{i+1} = x_{i-1} \oบวก F(x_i, k_i)$เพื่อเขียนใหม่ $F(x_i, k_i)$ เช่น $x_{i+1} \oบวก x_{i-1}$และอื่น ๆ:
$$ x_i[\alpha] \oplus \left(x_{i+1} \oplus x_{i-1}\right)[\beta] = k_i[\gamma] \tag{4} $$
นี่จะเป็นขอบในกราฟของเรา นั่นคือ สำหรับการประมาณเชิงเส้นทั้งหมด และสำหรับรอบการสร้างอินสแตนซ์ทั้งหมด $i$เราสามารถสร้างขอบดังกล่าวได้ หากแหล่งที่มาของขอบเป็นสมการ $(1)$, เป้าหมายของขอบคือสมการต่อไปนี้, ได้รับโดย $\operatorname{XOR}$อิ้ง $(1)$ และ $(4)$:
$$ \bigoplus_{j=0}^{i-2} x_j[\delta_j] \oplus x_{i-1}[\delta_{i-1} \oplus \beta] \oplus x_i[\delta_i \oplus \alpha] \oplus x_{i+1}[\delta_{i+1} \oplus \beta] \bigoplus_{j=i+2}^{n+1} x_j[\delta_j] = k_i[\epsilon_j \oplus \gamma ] \bigoplus_{j=1}^n k_j[\epsilon_j] \แท็ก{5} $$
หนึ่ง $n$การประมาณรอบเป็นโหนดเช่น $(1)$ที่หน้ากาก $\delta_2 \dots \delta_{n-1}$ ล้วน $0$. นั่นคือ สมการเกี่ยวข้องกับข้อความธรรมดา ข้อความไซเฟอร์ และคีย์เท่านั้น
เราเริ่มการค้นหากราฟด้วยการประมาณเล็กน้อย โดยที่ $\forall i, \delta_i = 0$, และ $\forall i, \gamma_i = 0$. เพื่อดูว่าเราจะใช้ขอบใด ระบบการตั้งชื่อเล็กน้อย:
เราจะได้เปรียบเท่านั้น $e$ที่นำเราจากโหนด $v: \bigoplus_{i=0}^{n+1} x_i[\delta_i] = \bigoplus_{i=1}^n k_i[\epsilon_i]$ ไปยังโหนด $w: \bigoplus_{i=0}^k x_i[\delta'_i] = \bigoplus_{i=1}^k k_i[\epsilon'_i]$เมื่อมีหน้ากากที่ซ่อนไว้ไม่เกิน 2 ชิ้น $w$ ไม่เป็นศูนย์
เรามาถึงสถานะสิ้นสุดเมื่อมาสก์ที่ซ่อนอยู่ทั้งหมดเป็นศูนย์ และเราไม่ได้อยู่ที่โหนดเริ่มต้น
เราใช้ lemma ซ้อนขึ้นเพื่อคำนวณน้ำหนักที่เราไป ซึ่งเราสามารถทำได้ใน logspace เพื่อปรับปรุงความแม่นยำ
ด้านล่างนี้คือซอร์สโค้ด C++ เพื่อจำลองตารางผลลัพธ์ของ Matsui ในภาคผนวก ฉันใช้อัลกอริทึมของ Dijkstra สำหรับการค้นหากราฟ แต่จริงๆแล้วมันมากเกินไป โซลูชันการเขียนโปรแกรมแบบไดนามิกก็สามารถทำได้เช่นกัน นี่เป็นเพราะเส้นทางเดียวที่เราสนใจกำลังเพิ่มขึ้นในตำแหน่งที่พวกเขาใช้การประมาณแบบหนึ่งรอบ (กล่าวคือ พวกเขาเริ่มต้นด้วยการประมาณที่ว่างเปล่า และนำไปใช้ที่รอบ เช่น 1, 2, 3, 5, 6, 8, 9, 10 และเข้าถึงสภาวะสุดท้าย) อย่างไรก็ตาม Dijkstra ทำงานทันที ดังนั้นไม่จำเป็นต้องคิดมาก
สิ่งเดียวที่เจาะจง DES ที่นี่คือการประมาณแบบหนึ่งรอบ หนึ่งรอบ_ค่าประมาณ. การแก้ไขที่ทำให้พบโซ่เชิงเส้นสำหรับเครือข่าย Feistel ใด ๆ โดยให้การประมาณกับฟังก์ชันรอบ
สำหรับ NUM_ROUNDS = 10, เอาต์พุตรหัสนี้:
การประมาณที่ดีที่สุด:
round_number: 10
มาสก์สถานะ = [1: [7, 18, 24, 29], 10: [15], 11: [7, 18, 24, 29]]
คีย์มาสก์ = [1: [22], 2: [44], 3: [22], 5: [22], 6: [44], 7: [22], 9: [22]]
ค่าประมาณที่ใช้: [-ACD-DCA-A]
ความน่าจะเป็น: 0.500047
Log2 (อคติ): -14.3904
ซึ่งตรงกับกระดาษของมัตสึอิพอดี
// ค้นหาโซ่ของการประมาณเชิงเส้นใน Feistel cipher
//
// รอบของ Feistel cipher สามารถอธิบายได้ดังนี้:
// x0 x1
// | ก |
// | | |
// วี วี |
// + <- F ---
// | |
// วี วี
// x2
//
// โดยที่ + คือ xor ในระดับบิต และ F คือฟังก์ชันการเรียงสับเปลี่ยนคีย์ พีชคณิต
// x2 = x0 + F(k, x1) (1)
// เส้นลวดที่บรรจุ x1 ยังคงไม่ถูกแก้ไข และจะถูกแทนที่ด้วย x2
// ก่อนรอบต่อไปในเครือข่าย Feistel เครือข่ายทั้งหมดก็ดู
// แบบนี้ โดยที่ ===><== หมายถึงเราสลับสายทั้งสอง:
// x0 x1
// | k1 |
// | | |
// วี วี |
// + <- F ---
// | |
// วี วี
// x2 x1
// | |
// x1===><==x2
// | |
// | k2 |
// | | |
// วี วี |
// + <- F ---
// | |
// วี วี
// x3 x2
// | |
// ...
//
//
// การประมาณหนึ่งรอบสำหรับ F คือสามบิตมาสก์ อัลฟ่า เบต้า แกมมา เช่น
// นั่น
// x[อัลฟา] + F(x, k)[เบต้า] = k[แกมมา]
// ถือด้วยความน่าจะเป็น p ที่นี่สัญกรณ์ a[m] หมายความว่าเรา xor the
// บิตในสตริงบิต a ซึ่งระบุโดยมาสก์ m ดังนั้น a[0b101] หมายถึง
// ((ก & 100) >> 2) ^ (ก & 1).
//
// เราสังเกตว่าสมการ (1) บอกเราว่า F(k, x1) = x2 ^ x0 โดยทั่วไปถ้าเรา
// ดูที่ i-th รอบ สมการ (1) บอกเราว่า
// F(x_{i + 1}, k_{i + 1}) = x_{i + 2} + x_i (2)
//
// ดังนั้น ถ้าเรามีค่าประมาณดังนี้
//
// x[อัลฟา] + F(x, k)[เบต้า] = k[แกมมา]
//
// เราสามารถยกตัวอย่างในรอบใดก็ได้ เช่น
//
// x1[อัลฟา] + F(x1, k1)[เบต้า] = k1[แกมมา]
//
// แล้วใช้สมการ (2) เขียนใหม่เป็น:
//
// x1[อัลฟา] + (x2 + x0)[เบต้า] = k1[แกมมา]
//
// ด้วยวิธีนี้ เราได้สมการสำหรับค่าของเส้นลวดใน Feistel
//เครือข่าย. โดยทั่วไปมักจะอยู่ในรูปแบบ:
//
// x_{i + 1}[alpha] + (x_{i + 2} + x_i)[beta] = k_{i + 1}[gamma] (3)
//
// เป้าหมายของเราคือการเริ่มต้นด้วยสมการง่ายๆ:
//
// x0[0] + x1[0] = 0
//
// ซึ่งมีค่าความน่าจะเป็นเป็น 1 และนำสมการเหล่านี้ไปใช้ ก็จะได้ค่า an
// สมการที่เกี่ยวข้องเท่านั้น:
// * x0 คำสูงในข้อความธรรมดา
// * x1 คำต่ำในข้อความธรรมดา
// * x_{n+1} คำสูงในไซเฟอร์เท็กซ์
// * x_n คำต่ำในไซเฟอร์เท็กซ์
// * แป้นกลมบาง k_i.
// และเราต้องการทราบความน่าจะเป็นที่พวกเขาถือ เราเรียกลักษณะนี้ว่า
// ของสมการ การประมาณเชิงเส้นของรหัสเต็ม
//
// โปรแกรมนี้พิจารณากราฟที่แต่ละโหนดอยู่ในรูปแบบ:
// (m_0, m_1, ..., m_{N+1}, km_0, km_1, ..., km_0, p)
// โดยที่ N คือจำนวนรอบ แต่ละ m_i เป็นบิตมาสก์ 32 บิต แต่ละ km_i เป็น
// bitmask 64 บิต และ p คือความน่าจะเป็น ความหมายของโหนดนี้คือ:
//
// ด้วยความน่าจะเป็น p
// (\sum_{i=0}^{N + 1} x_i[m_i]) + (\sum_{i=0}^{N-1} k_i[km_i]) = 0
//
// โดยที่ x_i คือค่าของสายไฟในเครือข่าย Feistel, k_i คือ
// แป้นกลม m_i เป็นบิตมาสก์สำหรับ x_i และ km_i เป็นมาสก์สำหรับ k_i
//
// เริ่มต้นที่โหนด โดยที่ m_i = 0 forall i และ km_j = 0 forall j และ p =
// 1 เราต้องการเข้าถึงสถานะที่แสดงถึงการประมาณเชิงเส้นของ
// ตัวเลขเต็ม
//
// ขอบของกราฟนี้จะใช้การประมาณ 1 รอบ
// สร้างอินสแตนซ์ในบางรอบในเครือข่าย ตัวอย่างเช่น ถ้าเรามีโหนด
//
// x_0[0b101] + x_1[0b11] = k_1[0b110] (4)
//
// และเรารู้สมการของแบบฟอร์ม (3):
// x_{i+1}[0b1011] + (x_{i + 2} + x_i)[0b11] = k_{i + 1}[0b101]
//
// เรายกตัวอย่างสิ่งนี้ได้ที่ i = 1 เพื่อให้ได้
//
// x_2[b1011] + (x_3 + x_1)[0b11] = k_2[0b101] (5)
// ถ้าเรา xor สมการนี้ (5) กับ (4) เราจะได้
//
// x_0[0b101] + x_2[0b1011] + x_3[0b11] = k_1[0b110] + k_2[0b101]
//
// ซึ่งเป็นโหนดอื่นในกราฟของเรา ด้วยวิธีนี้เราจะสำรวจกราฟจนกว่าเราจะ
// เข้าถึงค่าประมาณเชิงเส้นของรหัสเต็ม
#include <อาร์เรย์>
#รวม <cstdint>
#รวมถึง <iostream>
#รวม <set>
#รวม <unordered_map>
#รวม <cassert>
#รวม <เวกเตอร์>
#รวม <cmath>
#รวม <ไม่บังคับ>
constexpr size_t NUM_ROUNDS = 10;
// แสดงบิตมาสก์ 64 บิต โดยแสดงเฉพาะดัชนีบิตที่ "เปิด"
std::ostream& show_mask(std::ostream& o, uint64_t m) {
int ฉัน = 0;
บูลก่อน = จริง;
o << "[";
ในขณะที่ (ม.) {
ถ้า (m & 1) {
ถ้า (! first) {
o << ",";
} อื่น {
อันดับแรก = เท็จ;
}
o << ฉัน;
}
ม >>= 1;
++ผม;
}
o << "]";
กลับ o;
}
// ความหมายของการประมาณนี้คือด้วยความน่าจะเป็น p = ความน่าจะเป็น (),
// x[อัลฟา] + F(x, k)[เบต้า] = k[แกมมา]
// สำหรับสตริง x 32 บิตใดๆ และสตริง k 48 บิต
//
// อคติกำหนดเป็น |ความน่าจะเป็น() - 0.5|
โครงสร้าง OneRoundApproximation {
ชื่อ const char*;
uint32_t อัลฟา;
uint32_t เบต้า;
uint64_t แกมมา; // ต้องการเพียง 48 บิต
log2_bias สองเท่า; // log_2 (อคติ)
ความน่าจะเป็นสองเท่า () const {
x สองเท่า = std::pow(2.0, log2_bias) + 0.5;
ส่งคืน std::max(x, 1.0 - x);
}
ตัวดำเนินการอัตโนมัติของเพื่อน<=>(const OneRoundApproximation&,
const OneRoundApproximation&) = ค่าเริ่มต้น;
เพื่อน std::ostream& โอเปอเรเตอร์<<(std::ostream& o,
const หนึ่งรอบประมาณ & ra) {
o << รา.ชื่อ;
กลับ o;
}
};
// นี่คือค่าประมาณที่เกี่ยวข้องกับบิตข้อความธรรมดาบางส่วน ข้อความไซเฟอร์เท็กซ์
// บิต คีย์บิตบางส่วน และอาจเป็นบิตสถานะที่ซ่อนอยู่ในลักษณะเชิงเส้น
// ใช้มาสก์บิตคงที่
//
// 2 สถานะแรกคือคำธรรมดา 2 สถานะ 2 สถานะสุดท้ายคือ 2
// ciphertext words และทุก ๆ สถานะเป็นสถานะที่ซ่อนอยู่ - มันคือค่า
// ของสายในเครือข่าย Feistel
โครงสร้างประมาณ {
std::array<uint32_t, NUM_ROUNDS + 2> state_mask;
std::array<uint64_t, NUM_ROUNDS> round_key_mask;
std::array<std::ทางเลือก<OneRoundApproximation>, NUM_ROUNDS>
ใช้_ประมาณ;
int round_number;
ตัวดำเนินการเพื่อนอัตโนมัติ<=>(const การประมาณ&, const การประมาณ&) = ค่าเริ่มต้น;
เพื่อน std::ostream& โอเปอเรเตอร์<<(std::ostream& o, const การประมาณ& a) {
o << "round_number: " << a.round_number << std::endl;
o << "สถานะมาสก์ = [";
int cnt = 0;
สำหรับ (size_t i = 0; i < NUM_ROUNDS + 2; ++i) {
ถ้า (!a.state_mask[i]) ดำเนินการต่อ;
ถ้า (cnt++ > 0) o << ", ";
o << ฉัน << ":";
show_mask(o, a.state_mask[i]);
}
o << "]" << std::endl;
ct = 0;
o << "คีย์มาสก์ = [";
สำหรับ (size_t i = 0; i < NUM_ROUNDS; ++i) {
ถ้า (!a.round_key_mask[i]) ดำเนินการต่อ;
ถ้า (cnt++ > 0) o << ", ";
o << ฉัน << ":";
show_mask(o, a.round_key_mask[i]);
}
o << "]" << std::endl;
o << "ค่าประมาณที่ใช้: [";
สำหรับ (size_t i = 0; i < NUM_ROUNDS; ++i) {
auto ma = a.applied_approximations[i];
ถ้า (ma == std::nullopt) {
o << "-";
} อื่น {
o << *แม่;
}
}
o << "]" << std::endl;
กลับ o;
}
};
// นี่คือค่าประมาณที่มีความน่าจะเป็นที่กำหนด
struct ถ่วงน้ำหนักประมาณการ {
ประมาณ a;
log2_bias สองเท่า;
ความน่าจะเป็นสองเท่า () const {
x สองเท่า = std::pow(2.0, log2_bias) + 0.5;
ส่งคืน std::max(x, 1.0 - x);
}
};
std::array<หนึ่งรอบประมาณ 5> หนึ่งรอบ_ประมาณ = {{
{"A", 0x8000, 0x21040080, 0x400000, std::log2(std::abs(12.0/64.0 - 0.5))},
{"B", 0xd8000000, 0x8000, 0x6c0000000000ULL, std::log2(std::abs(22.0/64.0 - 0.5))},
{"C", 0x20000000, 0x8000, 0x100000000000ULL, std::log2(std::abs(30.0/64.0 - 0.5))},
{"D", 0x8000, 0x1040080, 0x400000, std::log2(std::abs(42.0/64.0 - 0.5))},
{"E", 0x11000, 0x1040080, 0x880000, std::log2(std::abs(16.0/64.0 - 0.5))}
}};
// ให้การประมาณที่มีอยู่ จะเกิดอะไรขึ้นถ้าเรา xor หนึ่งรอบ
// ประมาณบนมัน? โดยเฉพาะอย่างยิ่ง การประมาณหนึ่งรอบนั้นจะเป็น
// สร้างอินสแตนซ์ที่รอบ `ตำแหน่ง`
การประมาณค่า apply_one_round_approximation(ค่าประมาณ const& a,
const OneRoundโดยประมาณ& o,
ตำแหน่ง size_t) {
การประมาณ b = a;
b.round_number = ตำแหน่ง + 1;
b.state_mask[ตำแหน่ง] ^= o.beta;
b.state_mask[ตำแหน่ง + 1] ^= o.alpha;
b.state_mask[ตำแหน่ง + 2] ^= o.beta;
b.round_key_mask[ตำแหน่ง] ^= o.gamma;
b.applied_approximations[ตำแหน่ง] = o;
กลับข;
}
// ส่งคืนจำนวนสถานะที่ซ่อนอยู่ซึ่งมีมาสก์ที่ไม่ใช่ศูนย์ในค่าที่กำหนด
// การประมาณ
size_t HiddenSize(ประมาณ& b) {
size_t ผลลัพธ์ = 0;
สำหรับ (size_t i = 2; i < NUM_ROUNDS; ++i) {
ผลลัพธ์ += b.state_mask[i] != 0;
}
ส่งคืนผลลัพธ์
}
std:: vector <การถ่วงน้ำหนักประมาณ> การเปลี่ยน (
const WeightedApproximation& a, const OneRoundApproximation& o) {
// สำหรับการประมาณค่า j รอบแรกของรหัสที่กำหนด เราสามารถนำไปใช้ได้
// การประมาณรอบที่สถานะปัจจุบันในเครือข่าย Feistel
// หรืออันถัดไป นั่นคือการประมาณหนึ่งรอบของแบบฟอร์ม:
// อัลฟา * x_{i + 1} + เบต้า * (x_{i+2} + x_i) = แกมมา * k_i
// สามารถ xorred ไปยังสถานะปัจจุบันซึ่งเป็นรูปแบบ:
//
// \sum_{k=0}^N state_mask_k * x_k + \sum_{k=0}^N key_mask * key_i = 0
//
// โดยที่ผลรวมคือ xor ของทุกบิตในอาร์กิวเมนต์
//
// สิ่งนี้จะทำให้ state_masks บางส่วนเป็นศูนย์ และบางส่วนไม่เป็นศูนย์ เราต้องการเท่านั้น
// ทำการเปลี่ยนเมื่อจำนวนมาสก์ที่ไม่ใช่ศูนย์สำหรับสถานะที่ซ่อนอยู่คือ
// อย่างมากสุด 2 เพราะนี่คือทั้งหมดที่จำเป็นสำหรับความคืบหน้าใน
// เครือข่าย Feistel ที่เราเคยเห็น (DES) สถานะถูกซ่อนเมื่อไม่ใช่ x_1
// x_2, x_{N-1} หรือ x_N นั่นคือเมื่อไม่ใช่ข้อความธรรมดาทั้งสองแบบ
// คำหรือคำใดคำหนึ่งในสองคำที่เป็นรหัส
// สิ่งนี้สามารถทำได้เร็วขึ้นและประหยัดพื้นที่มากขึ้น แต่ฉันไม่ทำอย่างนั้นโดยเฉพาะ
//ดูแลตอนนี้.
// เราค้นหารอบที่จะยกตัวอย่างการประมาณหนึ่งรอบ
std::vector ผลลัพธ์ <การถ่วงน้ำหนักประมาณการ>;
สำหรับ (size_t i = a.a.round_number; i < NUM_ROUNDS; ++i) {
การประมาณ b = apply_one_round_approximation(a.a, o, i);
ถ้า (HiddenSize(b) > 2) ดำเนินการต่อ;
ผลลัพธ์ push_back (
{.a = std::move(ข),
.log2_bias = 1 + a.log2_bias + o.log2_bias});
}
ส่งคืนผลลัพธ์
}
std::ostream& โอเปอเรเตอร์<<(std::ostream& o, const WeightedApproximation& wa) {
o << wa.a << std::endl;
o << "ความน่าจะเป็น:" << wa.probability() << std::endl;
o << "Log2(Bias):" << wa.log2_bias << std::endl;
กลับ o;
}
// เป็นเพียงฟังก์ชันแฮชมาตรฐานที่สามารถใส่ค่าประมาณในแฮชได้
// ตาราง.
แม่แบบ <คลาส T>
โมฆะแบบอินไลน์ hash_combine (std::size_t& seed, const T& v) {
std::hash<T> แฮชเชอร์;
เมล็ด ^= hasher(v) + 0x9e3779b9 + (เมล็ด << 6) + (เมล็ด >> 2);
}
size_t HashApproximation (การประมาณค่า const& a) {
size_t h = 0;
สำหรับ (size_t i = 0; i < NUM_ROUNDS + 2; ++i) {
hash_combine(h, a.state_mask[i]);
}
hash_combine(h, a.round_number);
กลับ h;
};
int หลัก () {
// เราจะใช้อัลกอริทึมของ Dijkstra เพื่อสำรวจกราฟนี้ น้ำหนักของขอบ
// คือ log2 ของอคติของการประมาณแบบหนึ่งรอบที่มันแทน
เปรียบเทียบอัตโนมัติ_by_probability = [](const WeightedApproximation& a,
const การถ่วงน้ำหนักโดยประมาณ& b) {
ถ้า (a.log2_bias > b.log2_bias) คืนค่าจริง;
ถ้า (a.a.round_key_mask < b.a.round_key_mask) คืนค่าจริง;
กลับ Hash ประมาณการ (a.a) < Hash ประมาณการ (b.a);
};
// นี่คือคิวของโหนดที่เรายังต้องเยี่ยมชม
std::set<WeightedApproximation, decltype(compare_by_probability)> คิว;
// สิ่งนี้บอกเราว่าโหนดใดได้รับการเยี่ยมชมแล้ว หมายเหตุในคิวที่เราจัดเก็บ
// โหนดที่มีน้ำหนัก ในขณะที่แฮชนี้เก็บเพียงค่าประมาณ
// เองโดยไม่มีความน่าจะเป็น นี้เพื่อให้สามารถปรับเปลี่ยนประมาณการได้
// น้ำหนักของการประมาณแต่ละครั้งเมื่อเราสำรวจกราฟ ตามของ Dijkstra
// อัลกอริทึม
std::unordered_map<ค่าประมาณ, decltype(queue.begin()),
decltype(&แฮชการประมาณค่า)>
เห็น (1, &Hash ประมาณ);
// การประมาณเริ่มต้นของเราไม่มีมาสก์ และมีความน่าจะเป็น 1 และ
// ดังนั้น bias ของมันคือ 1 - 0.5 = 0.5..
WeightedApproximation wa = {.a = การประมาณค่า{},
.log2_bias = std::log2(0.5)};
อัตโนมัติ = คิวแทรก (วา) อันดับแรก;
saw.emplace(วะ มัน);
// เราติดตามการประมาณที่ดีที่สุดเท่าที่เราเคยเห็นมา เพียง
// การประมาณค่าที่เราจะสนใจคือค่าประมาณที่เกี่ยวข้องกับข้อความธรรมดา
// ciphertexts และคีย์บิต สำหรับสิ่งนี้จะต้องมีจำนวนรอบ
// NUM_ROUNDS ซึ่งหมายความว่า `wa` ไม่ใช่ค่าประมาณที่ดีที่สุดที่ถูกต้อง
// ตัวเลขเต็ม และจะถูกเขียนทับในครั้งแรกที่เราพบว่าถูกต้อง
// การประมาณ
WeightedApproximation best_approximation = wa;
ในขณะที่ (!queue.empty()) {
WeightedApproximation v =queue.extract(queue.begin()).value();
// เราส่งสัญญาณว่าได้ออกจากคิวแล้ว
เห็น [v.a] = คิวสิ้นสุด ();
// ถ้านี่เป็นค่าประมาณของรหัสเต็ม (เช่น NUM_ROUNDS ทั้งหมดจาก
// มัน) และไม่เกี่ยวข้องกับสถานะที่ซ่อนอยู่ (เช่น ข้อความธรรมดาเท่านั้น
// ciphertexts และคีย์บิต) จึงเป็นตัวเลือกที่ดีสำหรับสิ่งที่ดีที่สุด
// การประมาณเชิงเส้นสำหรับรหัสทั้งหมด เราจะรักษาโอกาสให้ได้มากที่สุด
// หนึ่ง นั่นคือคนที่มีอคติสูงสุด
ถ้า (v.a.round_number == NUM_ROUNDS && HiddenSize(v.a) == 0) {
ถ้า (best_approximation.a.round_number == 0 ||
best_approximation.log2_bias < v.log2_bias) {
best_approximation = v;
}
ดำเนินต่อ;
}
// ตอนนี้เราสำรวจขอบทั้งหมดที่ออกจากการประมาณค่า 'v' โดยแสดงรายการทั้งหมด
// การประมาณแบบรอบเดียวที่เป็นไปได้ เราสามารถใช้การประมาณนี้ได้
สำหรับ (const อัตโนมัติ& o : one_round_approximations) {
สำหรับ (การถ่วงน้ำหนักโดยประมาณ w : การเปลี่ยน (v, o)) {
อัตโนมัติ = saw.find(w.a);
ถ้า (มัน == saw.end()) {
// ถ้าเราไม่เคยเห็นค่าประมาณนี้มาก่อน ให้เพิ่มเข้าไปในคิว
// และทำเครื่องหมายว่าเห็นแล้ว นี่ต้องเป็นองค์ประกอบใหม่ในคิวและ
// เรายืนยันเช่นนั้น
อัตโนมัติ [jt, แทรก] = คิวแทรก (std::move (w));
ยืนยัน(แทรก);
saw.emplace(jt->a, std::move(jt));
} อื่น {
//เราเคยดูแล้ว ถ้าเราดึงมันออกจากคิวแล้ว
// ไม่ต้องทำอะไร เราพบเส้นทางน้ำหนักที่สั้นที่สุดแล้ว
// ไปที่อัลกอริทึมที่ไม่แปรเปลี่ยนของ Dijkstra ..
ถ้า (it->วินาที == คิวสิ้นสุด ()) ดำเนินการต่อ;
// ผ่อนคลายขอบถ้าเป็นไปได้
ถ้า (it->วินาที->log2_bias < w.log2_bias) {
คิว ลบ (มัน -> วินาที);
auto jt = คิว.แทรก(w).ก่อน;
it->วินาที = jt;
}
}
}
}
}
std::cout << "การประมาณที่ดีที่สุด: " << std::endl
<< ค่าประมาณที่ดีที่สุด << std::endl;
}
```
คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา
