حمله مسگر

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در دانش رمزنگاری، حمله مسگر (Coppersmith's Attack) یک کلاس از حملات را بر روی کلید عمومی RSA cryptosystem بر اساس قضیه مسگر توصیف می‌کند. در این مقاله نشان خواهیم داد که چگونه می توان الگوریتم 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=۳%7B%7Bسخ}}

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)%7B%7Bسخ}}

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))%7B%7Bسخ}}

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 کوچک باشد و یا اگر دانش بخشی از کلیدهای مخفی در دسترس باشد.