CRT Şifre Çözme Hızlandırma Hesaplayıcı

Bu hesaplama hakkında

RSA şifre çözme normalde m = c^d mod n işlemini doğrudan hesaplar; d genellikle 2048 bit uzunluğunda olduğundan bu oldukça maliyetli bir modüler üs alma işlemidir. Çin Kalan Teoremi (CRT) optimizasyonu bu işlemi, n'nin asal çarpanları p ve q modunda iki daha küçük üs almaya böler: indirgenmiş üsler dp = d mod (p−1) ve dq = d mod (q−1) kullanılarak m_p = c^dp mod p ve m_q = c^dq mod q hesaplanır.

p ve q, n'nin yaklaşık yarısı kadar bit uzunluğunda olduğundan bu iki üs alma işlemi tek başına çok daha ucuzdur; m_p ve m_q'yu Garner formülü ile birleştirmek tam mesajı m geri verir. Sonuç, düz modüler üs almaya kıyasla yaklaşık 4× hızlanmadır — bu yüzden CRT tabanlı şifre çözme, TLS yığınlarında ve OpenSSL gibi kriptografi kütüphanelerinde varsayılan uygulama yöntemidir ve RSA özel anahtarları genellikle yalnızca d yerine p, q, dp, dq ve qInv ile saklanır.