Bakırcı yöntemi - Coppersmith method

Bakırcı yöntemi, öneren Don Bakırcı, küçük tamsayı bulma yöntemidir sıfırlar tek değişkenli veya iki değişkenli polinomlar belirli bir tamsayı modulo. Yöntem, Lenstra – Lenstra – Lovász kafes temel indirgeme algoritması (LLL) hedef polinomla aynı sıfırlara ancak daha küçük katsayılara sahip bir polinom bulmak için.

İçinde kriptografi Coppersmith yöntemi esas olarak RSA ne zaman gizli anahtar bilinir ve bir temel oluşturur Bakırcı saldırısı.

Yaklaşmak

Coppersmith'in yaklaşımı, modüler polinom denklemleri çözmenin tamsayılar üzerinden polinomları çözmeye indirgenmesidir.

İzin Vermek ${ displaystyle F (x) = x ^ {n} + a_ {n-1} x ^ {n-1} + ldots + a_ {1} x + a_ {0}}$ ve varsayalım ki ${ displaystyle F (x_ {0}) eşdeğeri 0 { pmod {M}}}$ bir öğretmen için ${ displaystyle | x_ {0} |$.Coppersmith’in algoritması bu tamsayı çözümünü bulmak için kullanılabilir ${ displaystyle x_ {0}}$.

Kökleri bulmak Q kullanımı kolaydır, ör. Newton yöntemi, ancak böyle bir algoritma bir bileşik sayıyı modulo olarak çalışmaz M. Coppersmith'in yönteminin arkasındaki fikir, farklı bir polinom bulmaktır. f ile ilgili F aynı köke sahip ${ displaystyle x_ {0}}$ modulo M, ancak yalnızca küçük katsayılara sahiptir. Katsayılar ve ${ displaystyle x_ {0}}$ yeterince küçük ${ displaystyle | f (x_ {0}) |$ tamsayıların üzerinde, o zaman elimizde ${ displaystyle f (x_ {0}) = 0}$, Böylece ${ displaystyle x_ {0}}$ kökü f bitmiş Q ve kolayca bulunabilir. Daha genel olarak, bir polinom bulabiliriz ${ displaystyle f (x)}$ aynı kök ile ${ displaystyle x_ {0}}$ biraz güç modulo ${ displaystyle M ^ {a}}$ nın-nin M, doyurucu ${ displaystyle | f (x_ {0}) |$ve çöz ${ displaystyle x_ {0}}$ yukarıdaki gibi.

Coppersmith'in algoritması, Lenstra – Lenstra – Lovász kafes temel indirgeme algoritması (LLL) polinomu oluşturmak için f küçük katsayılarla. F, algoritma polinomları oluşturur ${ displaystyle p_ {1} (x), p_ {2} (x), noktalar, p_ {n} (x)}$ hepsi aynı köke sahip ${ displaystyle x_ {0}}$ modulo ${ displaystyle M ^ {a}}$, nerede a derecesine göre seçilen bir tam sayıdır F ve boyutu ${ displaystyle x_ {0}}$.Hiç doğrusal kombinasyon Bu polinomların arasında ayrıca ${ displaystyle x_ {0}}$ kök modulo olarak ${ displaystyle M ^ {a}}$.

Sonraki adım, doğrusal bir kombinasyon oluşturmak için LLL algoritmasını kullanmaktır. ${ displaystyle f (x) = toplamı c_ {i} p_ {i} (x)}$of ${ displaystyle p_ {i} (x)}$ böylece eşitsizlik ${ displaystyle | f (x_ {0}) |$ Artık standart çarpanlara ayırma yöntemleri sıfırları hesaplayabilir ${ displaystyle f (x)}$ tamsayılar üzerinde.

Referanslar

• D. Coppersmith (1996). Tek Değişkenli Modüler Denklemin Küçük Bir Kökünü Bulmak. Bilgisayar Bilimlerinde Ders Notları. 1070. s. 155–165. doi:10.1007/3-540-68339-9_14. ISBN  978-3-540-61186-8.
• D. Coppersmith (1996). İki Değişkenli Tamsayı Denkleminin Küçük Bir Kökünü Bulmak; Bilinen yüksek bitlerle faktoring. Bilgisayar Bilimlerinde Ders Notları. 1070. sayfa 178–189. doi:10.1007/3-540-68339-9_16. ISBN  978-3-540-61186-8.
• Bauer, A .; Joux, A. (2007). Bakırcı Algoritmasının Üç Değişkenli Titiz bir Varyasyonuna Doğru. Bilgisayar Bilimlerinde Ders Notları. 4515. sayfa 361–378. doi:10.1007/978-3-540-72540-4_21. ISBN  978-3-540-72539-8.