RSA với số mũ là một yếu tố của mô đun

Ý tưởng chính ở đây là $m_1$ (hoặc $m_2$) là rất nhỏ so với mô đun. Điều này cho phép chúng tôi áp dụng các kỹ thuật Coppersmith thông thường.

Chúng ta biết rằng $c_1 = m_1^p \bmod n$, đòi hỏi $c_1 \equiv m_1 \bmod p$. Từ đó chúng ta biết rằng $c_1 - m_1 = t\cdot p$, đối với một số $t$. Nói cách khác, $\gcd(c_1 - x, n) = p \ge n^{1/2}$ cho một số $x = m_1 \le n^{1/4}$. Ở đây mong đợi của chúng tôi $x = m_1$ nhỏ hơn nhiều so với $n^{1/4}$, trên thực tế, điều này làm cho mọi thứ dễ tính toán hơn.

Điều này có thể dễ dàng tái tạo trong Sage:

hiền nhân: p = random_prime(2^1024, lbbound=2^1023+2^1022)                                                                                                          
hiền nhân: q = random_prime(2^1000, lbbound=2^999+2^998)                                                                                                            
hiền nhân: n = p*q                                                                                                                                                 
Hiền nhân:                                                                                                                                                         
hiền triết: m1 = randint(0, 2^200)                                                                                                                                  
hiền triết: m2 = randint(0, 2^200)                                                                                                                                  
hiền nhân: c1 = power_mod(m1, p, n)                                                                                                                                
hiền nhân: c2 = power_mod(m2, q, n)                                                                                                                                
Hiền nhân:                                                                                                                                                         
hiền triết: P.<x> = Zmod(n)[]                                                                                                                                       
hiền triết: f = (c1 - x).monic()                                                                                                                                    
nhà hiền triết: f.small_roots(beta=0.5)                                                                                                                                 
[1106883791702122199703869965196585780508362129433642126297878]
hiền triết: m1                                                                                                                                                      
1106883791702122199703869965196585780508362129433642126297878

phục hồi $m_2$ có thể được thực hiện theo cách tương tự hoặc bằng cách khôi phục các yếu tố một lần $m_1$ được phục hồi―$p = \gcd(c_1 - m_1, n)$âvà giải mã $m_2$ thông thường.