حمله مسگر

در دانش رمزنگاری، حمله مسگر (Coppersmith's Attack) یک کلاس از حملات را بر روی کلید عمومی آراس‌ای بر اساس قضیه مسگر توصیف می‌کند. در این مقاله نشان خواهیم داد که چگونه می‌توان الگوریتم Coppersmith برای پیدا کردن ریشه‌های کوچک از چندجمله‌ای‌ های مدولار چندگانه به کار برد، کلید عمومی در سیستم RSA (آراس‌ای) چند تایی از اعداد صحیح است، که در آن N است حاصل ضرب دو عدد اول p و q است.

کد زیر کلید RSA با مدول N از بیت‌ها N را تولید می‌کند، ایجاد یک چند جمله‌ای تصادفی:

f(x) = x2 + ax + b mod N

با ریشه کوچک |x0| <2n/3 و بازیابی این ریشه با استفاده از تکنیک مسگر:

def keyGen(n=۲۵۶):

"Generates an RSA key"

while True:

p=random_prime(2^(n//2));q=random_prime(2^(n//2));e=۳

if gcd(e,(p-1)*(q-1))==1: break

d=inverse_mod(e,(p-1)*(q-1))

Nn=p*q

print "p=",p,"q=",q

print "N=",Nn

print "Size of N:",Nn.nbits()

return Nn,p،q,e،d

def CopPolyDeg2(a,b،Nn):

"Finds a small root of polynomial x^2+ax+b=0 mod N"

n=Nn.nbits()

X=2^(n//3-5)

M=matrix(ZZ,[[X^2,a*X,b],\

[0 ,Nn*X,0],\

[0 ,0 ,Nn]])

V=M.LLL()

v=V[0]

return [v[i]/X^(2-i) for i in range(3)]

def test():

"""Generates a random polynomial with a small root x0 modulo Nn

and recovers his root."""

Nn,p،q,e،d=keyGen()

n=Nn.nbits()

x0=ZZ.random_element(2^(n//3-10))

a=ZZ.random_element(Nn)

b=mod(-x0^2-a*x0,Nn)

print "x0=",x0

v=CopPolyDeg2(a,b،Nn)

R.<x> = ZZ[]

f = v[0]*x^2+v[1]*x+v[2]

print find_root(f, 0,2^(n//3-10))

الگوریتم مسگر مبتنی بر یک نقص ساده در الگوریتم RSA است هنگامی که پیام‌ها درمقایسه با عدد عمومی N کوچک هستند.

قضیه مسگر دارای کاربردهای بسیاری را در حمله به RSA است به خصوص اگر توان عمومی e کوچک باشد یا اگر دانش بخشی از کلیدهای مخفی در دسترس باشد.