Ключевая идея здесь в том, что $m_1$ (или же $m_2$) очень мал по отношению к модулю. Это позволяет нам применить обычные методы копперсмита.
Мы знаем это $c_1 = m_1^p \bmod n$, что влечет за собой $c_1 \экв m_1 \bmod p$. Отсюда мы знаем, что $c_1 - m_1 = t\cdot p$, для некоторых $t$. Другими словами, $\gcd(c_1 - x, n) = p \ge n^{1/2}$ для некоторых $x = m_1 \le n^{1/4}$. Здесь наш ожидаемый $х = m_1$ намного меньше, чем $n^{1/4}$, на самом деле, что упрощает вычисления.
Это легко воспроизвести в Sage:
мудрец: p = random_prime (2 ^ 1024, lbound = 2 ^ 1023 + 2 ^ 1022)
мудрец: q = random_prime (2 ^ 1000, lbound = 2 ^ 999 + 2 ^ 998)
мудрец: n = p*q
мудрец:
мудрец: m1 = randint(0, 2^200)
мудрец: m2 = randint(0, 2^200)
мудрец: c1 = power_mod(m1, p, n)
мудрец: c2 = power_mod(m2, q, n)
мудрец:
мудрец: P.<x> = Zmod(n)[]
мудрец: f = (c1 - x).monic()
шалфей: f.small_roots (бета = 0,5)
[1106883791702122199703869965196585780508362129433642126297878]
шалфей: м1
1106883791702122199703869965196585780508362129433642126297878
Восстановление $m_2$ можно сделать таким же образом или путем восстановления факторов один раз $m_1$ восстанавливается$p = \gcd(c_1 - m_1, n)$и расшифровка $m_2$ обычно.
