RSA için, gizli üssü nasıl hesaplarım?

Question

RSA için, gizli üssü nasıl hesaplarım?

P ve q iki prim ve phi = (p-1) (q-1) ve genel üs (0x10001) verildiğinde, gizli üssü 'd' nasıl alabilirim?

Ben yapmak zorunda olduğunu okudum

: d = e ^-1 mod phimodular inversion ve euclidean equation kullanarak ama anlayamıyorum nasıl ya bir ^-1 ≡ x yukarıdaki formül harita modüler inversiyon wiki sayfasındaki mod m formülü veya bunun öklid GCD denklemiyle nasıl eşleştiği. Birisi lütfen yardım edebilir

, şerefe

Answer 1

Sen yaraşır d için çözmeye extended Euclidean algorithm kullanabilirsiniz

RSA şifreleme için

de = 1 mod phi(m) 

, e şifreleme anahtarı, d şifre çözme anahtarı olduğunu ve şifreleme ve şifre çözme, her ikisi de modülasyon modu m tarafından gerçekleştirilir. Anahtar e ile bir mesaj a şifrelemek ve ardından anahtar d kullanarak şifresini çözmek için, hesaplamak (a ^e) ^d bir de mod m =. Ama de = 1 mod phi(m) beri Euler's totient theorem de bir ^{bir mod m uyumlu olduğunu söyler - diğer bir deyişle, orijinal a geri almak.}

yüzden RSA şifreleme güvenli olduğuna inanılan çarpanlara m = pq, bilmeden, sadece e anahtar şifreleme ve modül m bilerek şifre çözme anahtarı d elde etmek bilinen hiçbir verimli yolu vardır.