Antik Çin savaşları bize Hack ile ilgili ne öğretti?

Diyelim ki büyük bir ordu var. General askerlerin 50 kişilik gruplara ayrılmalarını istiyor ve 4 kişinin grup dışında kaldığını görüyor. Sonra askerleri 60 kişilik gruplara ayırıyor ve geriye 14 kişi kalıyor. Son kez 70 kişilik gruplara ayrılıyorlar ve geriye 24 kişi kalmış oluyor. Ardından general bu verilerden yararlanarak ordunun 201,554 kişilik olduğunu hesaplıyor. Peki ya bunu nasıl yapıyor?

>>> ordu%50

4

>>> ordu%60

14

>>> ordu%70

24

>>> print (ordu)

201554

Çin Kalan Teoremi (ÇKT), ilk olarak Çinli matematikçi Sun Tzu tarafında yayınlanmıştı. Bu teorem, belirtilen değerlere bölündüğü takdirde belirtilen kalanları verecek bir bilinmeyeni hesaplamaya yarıyor. Aynı açık anahtar şifreleyicileri gibi ÇKT de şifrelenmiş mesajları kırabilir. O halde aşağıdaki eşitlikte x’in değeri ne olur:

x mod 3 = 2
x mod 5 = 3
x mod 7 = 2

Cevap 23’dür çünkü 23 bölü 3’ün kalanı 2, 23 bölü 5’in kalanı 3, 23 bölü 7’nin kalanı 2’dir.

ÇKT ve RSA

Eğer yeteri kadar aynı e değeri ve farklı modül (N) değerlerine sahip şifreli RSA mesajı yakalarsak, mesajı Çin Kalan Teoremi (ÇKT) ile çözebiliriz. Örneğin eğer e değeri 3’e eşit ise mesajı deşifre etmemiz için 3 şifre mesajı gerekir.

Bunun için, aşağıdaki eşitlik kullanılabilir:

e=3,
message=123456789123456,
p1=1131701, q1=1131721,
p2=1131727, q2=1131737,
p3=1131749, q3=1131751

İşlem sonucu şu sonuç elde edilir:

eGCD of N values: 1
N1= 1280769787421 N2= 1280817319799 N3= 1280858062499
Message= 1234567891234 e= 3
Cipher1= 184224238921 Cipher2= 173356604414 Cipher3= 369941826218

Ardından çözmemiz gereken eşitlikler şunlardır:

M^e mod 1280769787421=184224238921
M^e mod 1280817319799=173356604414
M^e mod 1280858062499=369941826218

Ve şimdi Çin Kalan Teoremi’ni kullanırsak elde edeceğimiz sonuç aşağıdaki gibidir:

(M^e) Sonucu: 188,1676,377,431,587,319,857,436,861,793,600,904

Ardından şu işlemi uygularız: 10^(log10(M^e)/e) ve sonuç olarak 1234567891234’ün mesajını deşifre ederiz.

Burada deneyin.

Daha detaylı bir örnek burada.

Ee?

Werner Schindler [bu makalesinde], ÇKT’nin kullanılması durumunda RSA modülünün faktörleştirilmesinden kaynaklı oluşabilecek bir RSA zamanlama saldırısı zaafiyetini gündeme getirmişti. Çalışma, 1996 yılında Arjen Lenstra’nın bir optimizasyona (ÇKT) karşı yapılabilecek saldırıyı keşfetmesine dayanıyor. İmza hesaplanırken (RSA-CRT optimizasyonu kullanılması durumunda) bir hata üretilirse, saldırgan ilgili özel anahtarı bir imzadan kurtarabilir. Bu zaafiyet, “RSA-CRT anahtar sızıntısı” olarak bilinir.

Peki bundan nasıl korunuruz?

Bu saldırıdan korunmanın 2 yolu var. İlki e değerinin kopyalanan mesaj sayısından fazla olmasını sağlamak, öbürü ise her mesaja rastgele değerler vermek. Şu anki çoğu uygulamada e’nin değeri 65,537’dir.

Kaynak

Çeviren: Tan Siret Akıncı

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir

Bu web sitesi gizliliğinizi ihmal etmeyecek şekilde çerezler kullanır.