Bu üç geçişli değişim problemi için iki formül işe yarıyor, ancak bunlardan birinin neden işe yaradığını anlayamıyorum
Sorun bildirimi:
"Alice ve Bob kullanıcılarının 3 geçişli Diffie-Hellman protokolünü p = 101 ile yürüttüklerini varsayalım. Alice'in 1 = 19 ve Bob'un b 1 = 13 seçtiğini varsayalım. Eğer Alice m = 5 gizli mesajını p = 101'e göndermek istiyorsa Bob, Alice ile Bob arasında değiş tokuş edilen tüm mesajları göster. "
Resmi çözüm:
$a_2 = {a_1}^{-1}\bmod(p-1)=79$
$b_2=77$
Alice → Bob: $m^{a_1}\bmod p=37$
Bob → Alice: $80$
Alice → Bob: $56$
Bob elde eder $m$ değerlendirerek $56^{b_2}\bmod p=5$
Çözüm Birinin yardımını kullanarak yaptığım çözüm ( çevrimiçi olarak bu üç geçişli protokol hakkında çok özel bilgiler bulamadığım için ):
Alice:
$\begin{align} a_2&={a_1}^{p-2}\bmod(p-1)\\ &=19^{99}\bmod100\\ &=79\end{align}$
Bob:
$\begin{align} b_2&={b_1}^{p-2}\bmod(p-1)\\ &=13^{99}\bmod100\\ &=77\end{align}$
Alice'den Bob'a # 1:
$\begin{align} m_\text{AliceToBob1}&=m^{a_1}\bmod p\\ &=5^{19}\bmod101\\ &=37\end{align}$
Bob'dan Alice'e (# 1 - # 2 yok):
$\begin{align} m_\text{BobToAlice}&={m_\text{AliceToBob1}}^{b_1}\bmod p\\ &=37^{13}\bmod101\\ &=80\end{align}$
Alice'den Bob'a # 2:
$\begin{align} m_\text{AliceToBob2}&={m_\text{BobToAlice}}^{a_2}\bmod p\\ &=80^7\bmod101\\ &=56\end{align}$
Bob mesajı şu şekilde alır:
$\begin{align} m'&={m_\text{AliceToBob2}}^{b_2}\bmod p\\ &=56^{77}\bmod101\\ &=5\end{align}$
Benim sorum:
Resmi çözüm neden kullanıyor $a_2={a_1}^{-1}\bmod(p-1)=79$ onun yerine $a_2={a_1}^{p-2}\bmod(p-1)=79$ve bu tür bir problem bağlamında bu denklik nasıl gerekçelendirilebilir? ("Bu tür bir problem bağlamında" diyorum çünkü benim anladığım kadarıyla iki ifade her zaman eşdeğer değildir ).
Karışıklığımı netleştirmeme yardımcı olabilecek herhangi bir girdi BÜYÜK BİR ŞEKİLDE takdir edilecektir!
PS
- $a_1$ Alice'in şifreleme anahtarıdır
- $a_2$ Alice'in şifre çözme anahtarıdır
- $b_1$ Bob'un şifreleme anahtarıdır
- $b_2$ Bob'un şifre çözme anahtarı
Yanıtlar
TL; DR: ikinci yöntem yalnızca asalların kaybolan bir oranı için işe yarar $p$.
Soru arasındaki aynı ilişkiyi kullanır $a_1$ ve $a_2$Pohlig-Hellman simetrik şifresindeki gibi. Bunda:
- $p$ genel bir birincil parametredir,
- şifreleme anahtarı rastgele bir tamsayıdır $a_1$ aralarında asal ile$p-1$,
- şifre çözme anahtarı bir tamsayıdır $a_2$ öyle ki $a_1\,a_2=k\,(p-1)+1$ bir tam sayı için $k$.
- şifreleme $m\mapsto c=m^{a_1}\bmod p$, için $m$ içinde $[0,p)$,
- şifre çözme başına $c\mapsto m'=c^{a_2}\bmod p$ve tutar $m'=m$.
Kanıt: $$\begin{align} m'&=c^{a_2}\bmod p&&\text{by construction of $m '$}\\ &=(m^{a_1}\bmod p)^{a_2}\bmod p&&\text{since $c = m ^ {a_1} \ bmod p$}\\ &=m^{a_1\,a_2}\bmod p\\ &=m^{k\,(p-1)+1}\bmod p&&\text{by construction of $a_2$}\\ &=m^{(p-1)\,k}\,m^1\bmod p\\ &=(m^{p-1})^k\,m\bmod p\\ &=(m^{p-1}\bmod p)^k\,m\bmod p\\ &=1^k\,m\bmod p&&\text{per Fermat's little theorem}\\ &=m\bmod p\\ &=m&&\text{since $m$ is in $[1, p)$} \end{align}$$
Not: Fermat'ın küçük teoremi ,$p$ asal ve $m$ katı değil $p$, o tutar $m^{p-1}\bmod p=1$.
Uygun bir tam sayı $a_2$ve aralıktaki tek kişi $[0,p-1)\,$, dır-dir ${a_1}^{-1}\bmod(p-1)\,$: Çarpımsal tersinin arasında$a_1$ modulo $p-1$. Sorunun resmi çözümünde kullanılan budur .
Bu çarpımsal tersi hesaplamak için ders kitabı yöntemi Genişletilmiş Öklid algoritmasıdır . Pratik uygulamalar için, iki daha az değişken kullanan ve negatif miktarları asla değiştirmeyen bu varyantı tavsiye ederim .
Sorunun diğer çözümü yalnızca aynı şeyi hesaplayarak farklılık gösterir $a_2$ farklı bir formül kullanarak: ${a_1}^{p-2}\bmod(p-1)$. Yani soru şu şekilde özetlenebilir:
Asal için $p>2$, neden / ne zaman bu $a^{-1}\bmod(p-1)$ olarak hesaplanabilir $a^{p-2}\bmod(p-1)$ ?
Tanım olarak, $a^{-1}\bmod(p-1)$ tam sayıdır $x$ içinde $[0,p-1)$ ile $a\,x\bmod(p-1)=1$. Sadece ne zaman tanımlanır$a$ ile uyumludur $p-1$. Sorunun eşdeğer olduğu sonucu çıkar:
Asal için $p>2$, neden / ne zaman bu $a^{p-1}\bmod(p-1)=1$ hepsi için $a$ coprime to $p-1$?
Bu çoğu için $p$ soru dahil $p=101$, ama her zaman değil. En küçük karşı örnek$p=11$, $a=3$. Başka o$p=103$, $a=5$. Bunlar için ikinci yöntemi kullanarak doğrulanabilir.$p$ ve şifreleme anahtarları çoğu için yanlış şifre çözmeye yol açar $m$.
Bunlar, A337119 formundaki asallardır (bu durum için yaratılmıştır).
2 3 5 7 13 17 19 37 41 43 61 73 97 101 109 127 157 163 181 193 241 257 313 337 379 401 421 433 487 541 577 601 641 661 673 757 769 881 883 937 1009 1093 1153 1201 1249 1297 1321 1361 1459 1601 1621 1801 1861 1873
Bunlar aynı zamanda asallardır $p$ öyle ki $p-1$bir Novák-Carmichael numarasıdır A124240 ; veya eşdeğer asal sayılar$p$ öyle ki $\lambda(p-1)$ böler $p-1$ (nerede $\lambda$olan Carmichael fonksiyonu ). Hızla incelirler$p$ büyür.
Bu nedenle sorunun ikinci yöntemi genel olarak yanlıştır ve çoğu asal$p$Eldeki uygulama için ilgi çekici (çünkü büyük olduklarından: bin bit). Muhtemelen aşağıdaki gerçeğin yanlış bir uzantısı olarak geldi:$p$ asal $a^{-1}\bmod p\;=\;a^{p-2}\bmod p$ sürece $a$ katları $p$, Fermat'ın küçük teoremini takip eder .
Sorunun üç geçişli değişiminde, $m'$ Bob tarafından sonunda elde edilen $m$ dan beri $$\begin{align} m'&={m_\text{AliceToBob2}}^{b_2}\bmod p\\ &={({m_\text{BobToAlice}}^{a_2}\bmod p)}^{b_2}\bmod p\\ &={m_\text{BobToAlice}}^{a_2\,b_2}\bmod p\\ &={({m_\text{AliceToBob1}}^{b_1}\bmod p)}^{a_2\,b_2}\bmod p\\ &={m_\text{AliceToBob1}}^{b_1\,a_2\,b_2}\bmod p\\ &={(m^{a_1}\bmod p)}^{b_1\,a_2\,b_2}\bmod p\\ &=m^{a_1\,b_1\,a_2\,b_2}\bmod p\\ &=m^{(a_1\,b_1)\,(a_2\,b_2)}\bmod p\\ &=(m^{a_1\,a_2}\bmod p)^{b_1\,b_2}\bmod p\\ &=m^{b_1\,b_2}\bmod p\\ &=m \end{align}$$