HesapHanem

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

Mesajı kurtarmak için CRT parametreleri p, q, dp, dq ve şifreli metni girin.

Nasıl hesaplanır?

Asal sayılar p ve q, indirgenmiş üsler dp = d mod (p−1) ve dq = d mod (q−1) ile şifreli metin c verildiğinde araç, kare alıp çarpma yöntemiyle m_p = c^dp mod p ve m_q = c^dq mod q değerlerini hesaplar. Genişletilmiş Öklid algoritmasıyla qinv = q⁻¹ mod p bulur, h = qinv × (m_p − m_q) mod p oluşturur ve m = m_q + h × q ile birleştirir (Garner formülü).

Beş girdinin hepsi tam sayı değilse, p ve q 1'den büyük değilse, dp, dq veya c negatifse ya da q'nun p modunda tersi yoksa (yani p = q ise) sonuç gösterilmez. Her girdi 253 sınırı içinde kalmalı, p × q ise 64 bitlik bir tam sayıya sığmalıdır (yaklaşık 9,2 × 1018 altı); böylece mesaj tam olarak yazılabilir. p ve q'nun asallığı ile dp ve dq'nun tutarlılığı denetlenmez. ≈4× satırı sabit bir etikettir, ölçüm değildir.

Örnek hesaplama

Ders kitabı anahtarı: p = 61, q = 53 (n = 3233, d = 2753), dolayısıyla dp = 2753 mod 60 = 53 ve dq = 2753 mod 52 = 49. c = 2790 alalım. m_p = 279053 mod 61 = 4 ve m_q = 279049 mod 53 = 12 çıkar. 53'ün 61 modundaki tersi qinv = 38. h = 38 × (4 − 12) mod 61 = 1. Mesaj: m = 12 + 1 × 53 = 65. 65'i e = 17 ile şifrelemek tekrar 2790 verir; gidiş dönüş tutuyor.

Bu örneği dene →

Sık yapılan hatalar

  • dp ya da dq alanına tam özel üs d'yi yazmak. d mod (p−1) ve d mod (q−1) değerlerini kullanın; üs tutarsızsa araç yine bir sayı verir ama bu düz metin değildir.
  • p ile q'nun yerini değiştirip dp ve dq'yu eski sırada bırakmak. Her üs kendi asalıyla eşleşmelidir, yoksa m yanlış olur.
  • p veya q için bileşik sayı girmek. Asallık denetlenmez ve araç yine cevap verir: q = 53 iken p = 65 girmek kendinden emin bir 3.245 üretir, ama bu geçerli bir çözme değildir.
  • n = p × q'dan büyük bir şifreli metin girmek. Cevap girdiğiniz sayı için değil, c mod n için bulunur ve her zaman p × q'dan küçüktür.
  • Gerçek 2048 bitlik anahtar değerlerini yapıştırmak. 253'ü aşan girdiler (ya da 64 biti aşan p × q) sonuç göstermez; araç küçük anahtarlarla öğrenmek içindir, gerçek trafiği çözmek için değil.

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.

Bu faydalı oldu mu?

En fazla 3 tepki seçebilirsiniz.

Yorumlar (1)

  • Editör ekibi

    4 kat hızlanma sabit bir etikettir, bir süre ölçümü değildir. Arkasındaki fikir: yarı boyutlu sayılarla yapılan iki modüler üs alma, her biri yaklaşık sekizde bir maliyetlidir; toplam, tam boyutlu tek bir üs almanın yaklaşık dörtte biri eder. Araç yalnızca küçük ders kitabı anahtarlarını, p × q yaklaşık 9,2 × 10¹⁸ altında kalacak şekilde işler. Hangi anahtar boyutlarını denemek istersiniz?

Popüler hesaplayıcılar

Kredi Hesaplama

Aylık taksit, toplam faiz ve ödeme planını hesaplayın.

Yüzde Hesaplama

Yüzde değişim, indirim ve oran hesaplamaları.

İndirim Hesaplama

İndirimli fiyatı, kazancı ve indirim tutarını hesaplayın.

Vücut Kitle Endeksi (VKİ)

Boy ve kiloya göre vücut kitle endeksini hesaplayın.

Yaş Hesaplama

Doğum tarihinden bugüne tam yıl, ay ve gün cinsinden yaşınızı hesaplayın.

Bileşik Faiz Hesaplama

Ana para, faiz oranı ve süreye göre bileşik faizle nihai tutarı hesaplayın.

Tüm Hesaplayıcılar