RSA'da bir makale yazan lise öğrencisiyim ve çok küçük asal sayılarla örnek yapıyorum. Sistemin nasıl çalıştığını anlıyorum, ancak ömrüm için genişletilmiş öklid algoritmasını kullanarak özel anahtarı hesaplayamıyorum. İşte RSA: Genişletilmiş Öklid Algoritması ile özel anahtar hesaplaması
şimdiye kadar yapmış ne:- Ben asal sayılar p seçmiş = 37 ve q = 89 ve hesaplanan N = 3293
- ben hesapladım (p-1) (q -1) = 3168
- e ve 3168'in nispeten asal olmasını sağlamak için bir sayı seçtim. Bunu standart öklid algoritması ile kontrol ediyorum ve bu çok iyi çalışıyor. Benim e = 25 Şimdi
Sadece öyle ki d bulmak için Genişletilmiş Öklid Algoritması Kullanarak ed = 1 (mod 3168)
tatmin etmelidir özel anahtar d, hesaplamak zorunda + tN = 1 de -887 aldım • 25 + 7 • 3168 = 1. 7'yi atarım ve d = -887 alırım. Ancak bir mesajın şifresini çözmeye çalışmak, bu işe yaramıyor.
Kitabımdan 2281 olması gerektiğini biliyorum ve işe yarıyor, ancak bu sayıya nasıl ulaştıklarını anlayamıyorum.
Herkes yardımcı olabilir mi? Son 4 saat boyunca bu sorunu çözmeye çalıştım ve her yerde bir cevap aradık. Uzatılmış Öklid Algoritmasını el ile yapıyorum, ancak sonuç çalışmamdan beri hesaplamalarım doğru olmalı. Çok yakın olduğunuz önceden
sayesinde
Mads
Ninefingers'ın belirttiği gibi, sadece pozitif kalanını kullanın. Eşdeğerde, negatif bir güce 'x' yükseltmek için önce tersini hesaplar ve sonra bunu (-x) gücüne yükseltir ('xx negatif olduğu için -x' pozitiftir). –
"de + tN = 1" -887 • 25 + 7 • 3168 = 1 'e nasıl karıştığınız konusunda kafam karıştı. E = 25'i anlıyorum ama d, t ve N anlamlı değil. D, t ve N ne anlama geliyor? Ve neden 7'yi atmana izin veriliyor? Casey –