เป็นไปได้ไหมที่จะถอดรหัส Linear Congruential Generator ถ้าฉันรู้แค่โมดูลัสของเอาต์พุต

ตามความคิดเห็นที่แก้ไข คำถามเดิม: OP คาดเดาว่า 100 หลัก $y_n$ ใน $\{0,1,2,3,4,5\}$ ในความครอบครองของพวกเขาจะได้รับโดยใช้นิพจน์ C (++) ที่เทียบเท่ากับ แรนด์()%6 กับ แรนด์() ใช้ PRNG (ไม่ใช่การเข้ารหัส) ตาม Linear Congruential Generator โดยมีรหัสเทียบเท่ากับ

ยาว x;
int rand (โมฆะ) {
  x = 214013*x+2531011; // หรือเป็น 22695477*x+1
กลับ (int)((x>>16)&0x7FFF);
}

สังเกตว่า $x$ เป็นอย่างน้อย 32 บิต แต่มีเพียง 31 บิตลำดับล่างเท่านั้นที่สำคัญเนื่องจาก (x>>16)&0x7FFF และ C การแสดง ไม่ได้ลงนามยาว การคูณด้วยการตัดทอนบิตลำดับสูงที่ไม่พอดีกับตัวแปร

สรุปรายละเอียดการเขียนโปรแกรม การคาดเดาก็คือว่า $x$ วิวัฒนาการต่อ $x_{n+1}:=a\cdot x_n+b\bmod m$ กับ $m=2^{31}$ และ $(ก,ข)$ สำหรับค่าคงที่บางตัวที่เชื่อว่าเป็นอย่างใดอย่างหนึ่ง $(214013,2531011)$ หรือ $(22695477,1)$. และ แรนด์() เอาต์พุตบิต 30â¦16 ของ $x$ ด้วยเหตุนี้ $y_n:=\lชั้น x_n/2^{16}\rชั้น\bmod 6$ จะได้รับสำหรับ $n=0$ ถึง $99$ (โดยเมล็ดเป็นจำนวนเต็มไม่ทราบ $x_{-1}$ ในช่วงที่ไม่มีสาระสำคัญเนื่องจากเท่านั้น $x_{-1}\bmod m$ จะสำคัญ; และเราดีกว่าที่จะพยายามหา $x_0$ ถึงอย่างไร).

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

ใช่เป็นไปได้ด้วยความมั่นใจที่ยอดเยี่ยม สถานะที่มีประสิทธิภาพของ PRNG ที่พิจารณามี 31 บิต มีเพียงสอง PRNG ที่พิจารณา ซึ่งผ่านได้สำหรับการจำลอง ดังนั้นเราควรจะสามารถค้นหาสถานะของมันและสถานะใดที่ใช้กับอีกเล็กน้อย $31+1=32$ ข้อมูลเล็กน้อย และเราได้รับ $100\cdot\log_2(6)\ประมาณ258.5$ บิตซึ่งจะให้การยืนยันมากมาย

วิธีที่ง่ายที่สุดคือลองคาดเดาทั้งสองอย่าง $(ก,ข)$และสำรวจค่าที่เป็นไปได้ของ $x_0$. มีเพียง $2^{31}$รู้ $y_0$ อนุญาตให้ลดอย่างเป็นระบบโดยปัจจัยของ $6$. ต่อไปนี้ $y_i$ กำจัดเพิ่มเติม $5$ ผู้สมัครออกจาก $6$. หากไม่มีผู้สมัครรายใดรอดทั้งหมด $y_i$, สมมติฐานถูกหักล้าง หากพบการแข่งขันเราจะรู้ว่า $(ก,ข)$ เราใช้ และคำนวณเพิ่มเติมได้ $y_i$. การใช้งานที่มีความสามารถในภาษาที่คอมไพล์จะใช้เวลาเพียงวินาทีเดียวบนเดสก์ท็อปพีซีสมัยใหม่

แต่อาจต้องการทำลายสิ่งนี้แบบเรียลไทม์ด้วย CPU ที่ทันสมัย ​​\$0.5 ที่ทำงานจากแบตเตอรี่ \$0.2 หรือติดอยู่กับ เครื่องคิดเลขที่ตั้งโปรแกรมได้ของปี 1970หรือ อีเนียค. สังเกตว่า $6$ เป็นเลขคู่ และตัวหารคือ $2^{16}$. มันเป็นไปตาม $y_n\bmod 2$ เป็นบิต $16$ ของ $x_n$. ยังตั้งข้อสังเกตว่าตั้งแต่ $m$ เป็นกำลังสอง การเปลี่ยนแปลงบิตอิน $x_n$ ไม่เผยแพร่ไปยังบิตลำดับล่างของ $x_{n+1}$. ถ้าเป็นไปตามนั้นบิต 16 ของ $x_n$ ขึ้นอยู่กับเพียง 17 บิตต่ำของ $x_0$. เรารู้บิต 16 ของ $x_0$จึงต้องทดสอบมากที่สุด $2^{16}$ ตัวเลือกสำหรับบิต 15â¦0 ของ $x_0$. จากนั้นเราสามารถหาอีก 14 บิตตามด้านบน ที่ แบ่งแยกและพิชิต วิธีการจะช่วยให้จัดการกับพารามิเตอร์ที่ใหญ่กว่ามากได้ เช่น ตัวแปร x ประเภท uin64_t และ กลับ x>>33บนซีพียูสมัยใหม่

ฉันสงสัยว่าเราจะทำอย่างไรถ้า $a$, $ข$ และ/หรือ $m$ ไม่เป็นที่รู้จัก

หมายเหตุด้านบน:

• มันใช้แบบแผนหลักในวิทยาการคอมพิวเตอร์ (และการเข้ารหัสโดยมีข้อยกเว้นเล็กน้อยเช่น DES): บิตจะนับจาก 0 (บิตลำดับต่ำ) ดังนั้นหากจำนวนเต็มไม่เป็นลบ $v$ แสดงเป็นเลขฐานสองเป็น $k$ บิต $b_j$, แล้ว $v=\sum b_j$ กับ $0\le j<k$. ในการประชุม big-endian บิต 0 เขียนไว้ทางด้านขวา: $6\times7=42$ เป็นทศนิยม $110\times111=101010$ ในไบนารี่
• ตัวแปรคอมพิวเตอร์ x เป็นอย่างน้อย 32 บิต แต่เป็นเพียงลำดับต่ำ 31 บิต (0 ถึง 30) และใช้ใน $x_n$, ดังนั้น $0\le x_n<m=2^{31}$. ผลลัพธ์ของ แรนด์() เป็นอย่างน้อย 16 บิต แต่มีเพียงลำดับต่ำ 15 บิต (0 ถึง 14) สสาร และอื่น ๆ ทั้งหมดเป็นศูนย์ ดังนั้น $0\le$แรนด์()$\le$RAND_MAX$=2^{15}-1$. ถ้า $0\le ฉัน<15$ จากนั้นบิต $เจ$ ของเอาต์พุตของ แรนด์() จับคู่บิต $ญ+16$ ของ x. มันตามด้วยบิต 0 ของ $y_n$ ตรงกับบิต 16 ของ $x_n$.

(นอกเรื่อง) ความคิดเห็นเกี่ยวกับ รหัสปัจจุบัน:

• มันพยายามใช้การเร่งความเร็วที่ทำได้โดย 6 แม้กระทั่ง ฉันขอยืนยันว่านี่คือ ไม่ ต้องถึงเวลาดำเนินการเป็นวินาที ถ้า
  • เรา สำรวจค่าที่เป็นไปได้ของ $x_0$มากกว่าเมล็ดพันธุ์หลายขั้นตอนก่อนหน้านี้
  • เราใช้สิ่งนั้น $x_0$ เป็น 31 บิต ดังนั้นเราจึงสามารถจำกัดการค้นหาภายนอกเป็น [0, 0x7ffffffff] นั่นคือ $2^{31}$ ผู้สมัคร $x_0$.
  • เราใช้สิ่งที่เรารู้ $y_0$ดังนั้น $x_0=2^{16}\cdot(6\cdot u+ y_0)+v$ สำหรับ $0\le u<\lceil2^{15}/6\rceil$ และ $0\le v<2^{16}$ซึ่งจำกัดไว้ประมาณ $2^{31}/6$ ผู้สมัครรับเลือกตั้ง $x_0$.
  • เราเพิ่มประสิทธิภาพการทดสอบสำหรับการตรวจสอบผู้สมัคร $x_0$ ต่อต้าน $y_1$ ในวงในบน $v$.
• สาระสำคัญของ ไม่จำเป็น เร่งความเร็ว 6 เป็นเลขคู่ คือให้หาบิต 16â¦0 ของ $x_0$ จับคู่ค่า $y_0$ รวบรวมแล้วบิต 30â¦17 รหัสไม่ได้ทำอย่างนั้น! ด้วยการเร่งความเร็วนั้น เวลาในการดำเนินการจะลดลงเหลือมิลลิวินาที
• เราต้องการค่าเต็มของ $y_n$ รวบรวมไว้ (ทั้งในการค้นหาที่ไม่ได้ปรับให้เหมาะสม และส่วนที่สองของการค้นหาที่ปรับให้เหมาะสม) แต่ดูเหมือนว่าจะไม่มีในอินพุต ซึ่งผมเดาว่า $y_n\bmod2$. นอกจากนี้ ฉันไม่เข้าใจว่าทำไมมันถึงอยู่ในอาร์เรย์สองมิติ ผลลัพธ์[3][7].
• เมื่อไร $x_0$ พบ ถ้าจำเป็นต้องค้นหาเมล็ด (หรือค่อนข้างบิต 30â¦0 ของจำนวนนั้น) จำนวนขั้นตอนที่ทราบมาก่อน ซึ่งสามารถทำได้อย่างมีประสิทธิภาพโดยการเดินกลับ LCG โดยใช้ $x_{n-1}:=a^{-1}\,(x_n-b)\bmod m$ ที่ไหน $a^{-1}$ คือ ผกผันแบบแยกส่วน ของ $a$ โมดูโล $m$.

นี่คือรหัสการทำงาน ปราศจาก ตัวเลือกการเร่งความเร็ว (จึงสามารถทำงานกับโมดูลัสการลดขั้นสุดท้ายแบบคี่ได้ $r$ ที่คำถามมี 6). ลองออนไลน์!

#รวม <stdint.h>
#รวม <stdio.h>
#รวม <inttypes.h>

#define A 214013 // สำหรับ VC; 22695477 สำหรับ พ.ศ
#กำหนด B 2531011 // สำหรับ VC; 1 สำหรับ BC
#define R 6 // โมดูลัส ใน [2, 32768]
// static_assert(A > 0 && A % 8 == 5, "mod 8 ต้องเป็น 5");
// static_assert(B > 0 && B % 2 == 1, "B mod 2 ต้องเป็น 1");
// static_assert(R >= 2 && R <= 32768, "R ต้องอยู่ใน [2, 32768]");

// ตัดสินใจว่าโมดูโลลดลงเมื่อ R เป็นกำลังสอง
#define M ((uint32_t)(((R-1)&R)!=0 ? 0x8000 : R)<<16)

// ลำดับของ yn สำหรับ VC (a=214013, b=2531011), n=6, seed=1639326023
// ถ้า R เป็นกำลังสอง ceil(16/log2(R))+1 รายการก็เพียงพอแล้ว
// มิฉะนั้น นั่นคือรายการ ceil(31/log2(R)) ดังนั้น 12 สำหรับ R=6
const int16_t y[] = {
  0,5,3,0,4,3,1,0,4,5,4,4,4,5,5,3,0,2,0,5,4,5,0, // 0, 2,5,1,3,5,5,5,
};

// INVA ผกผันโมดูลาร์ของ A โมดูโล M
#กำหนด INVA (IN_A(IN_A(IN_A(IN_A((uint32_t)A))))&(M-1))
#กำหนด IN_A(v) (v*(2-v*A))

int main (โมฆะ) {
  // ตัดสินใจเริ่มต้น x0 เพื่อให้ตรงกับ y0
  const uint32_t y0 = y[0], y1 = y[1];
  int32_t x0 = (int32_t)(((M >> 16) - y0) / R * R + y0) << 16 | 0xffff;
  uint32_t พบ = 0;
  printf("ตัวสร้าง: ((int)((x = %" PRIu32 " * x + %" PRIu32 ") >> 16) & 0x7fff) %% %u\n",
    (uint32_t)A, (uint32_t)B, (ไม่ได้ลงชื่อ)R);
  ในขณะที่ (x0 >= 0) {
    uint32_t x1 = A * (uint32_t)x0 + B;
    ทำ {
      // ยืนยัน ( (x0 >> 16) % R == y0);
      // ยืนยัน ( x1 == A * (uint32_t)x0 + B);
      ถ้า (((x1 >> 16) & 0x7fff) % R == y1) {
        uint32_t x = x1;
        int n;
        สำหรับ (n = 2; n < sizeof(y) / sizeof(*y); ++n)
          ถ้า ((((x = A * x + B) >> 16) & 0x7fff) % R != y[n])
            ไปที่ nxt;
        // พบวิธีแก้ปัญหา
        x = (INVA * ((uint32_t)x0 - B)) & (M - 1);
        printf("x0 สามารถเป็น %" PRId32 " นั่นคือ seed=%" PRIu32
          " โมดูโล 0x%" PRIx32 ", ผลตอบแทน:\n", x0, x, M);
        // พิสูจน์ประเด็นโดยการแสดงผลลัพธ์
        สำหรับ (n = 0; n < sizeof(y) / sizeof(*y) + 8; ++n)
          printf(" %d", ((int)((x = A * x + B) >> 16) & 0x7fff) % R);
        printf("\n");
        ++พบ;
      }
    nxt: x1 -= (uint32_t)A;
    } ในขณะที่ (((x0--) & 0xffff) != 0);
    x0 -= (int32_t)(R - 1) << 16;
  }
  printf("found %" PRIu32 " solution%s\n", พบ, พบ > 1 ? "s" : "");
  กลับ 0;
}

// ยอมแพ้:
// ตัวสร้าง: ((int)((x = 214013 * x + 2531011) >> 16) & 0x7fff) % 6
// x0 สามารถเป็น 531633902 นั่นคือ seed=1639326023 โมดูโล 0x80000000 ซึ่งให้ผลลัพธ์:
// 2 3 4 1 5 1 1 5 4 0 3 2 2 5 5 3 5 5 3 4 0 1 1 4 1 3 3 2 5 4 4
// พบ 1 วิธีแก้ไข