Membuktikan bahwa fungsi enkripsi RSA dengan modulus bebas non-persegi bukan merupakan permutasi

Aug 19 2020

Berikut ini adalah latar belakang untuk pertanyaan yang ada. Saat belajar RSA saya sampai pada pertanyaan tentang apa yang terjadi jika$p$ dan $q$terlibat dalam komputasi modulus sebenarnya bukan bilangan prima? Sudah ada topik terkait tentang ini ( Mengapa RSA membutuhkan p dan q menjadi bilangan prima? ). Sementara sebagian besar jawaban bermuara pada pertimbangan efisiensi dan keamanan, terdapat satu jawaban yang menyatakan bahwa fungsi enkripsi RSA dengan modulus yang terdiri dari pangkat utama kehilangan sifat bijeksinya, yaitu bukan permutasi lagi. Namun perilaku ini hanya ditampilkan pada contoh tanpa bukti.

Mengingat itu, saya mulai mencari bukti properti permutasi RSA, dan saya menemukan bukti seperti itu di sini . Tetapi sekali lagi, itu menyatakan bahwa buktinya hanya berfungsi jika$p \ne q$, sementara tidak jelas mengapa ini bukan untuk $p = q$.

Kemudian saya mulai menggalinya sendiri. Sebenarnya, tampaknya cukup jelas$p = q$ kasus jika $p$adalah bilangan prima. Kemudian untuk$N = p^2$, kami mendapat satu set teks biasa $\{m_i\}$ seperti yang $0 \leq m_i < N$ dan $m_i \equiv 0\pmod{p}$, dan memiliki eksponen $e > 2$ kami juga mendapat $m_i^e \equiv 0\pmod{p^2}$.

Tapi saya tidak yakin bagaimana menggeneralisasi kasus $N = p^s, s > 2$; $N=p^sq, s > 1$; $N=p^sq^r, s > 2, r > 2$. Mari kita ambil kasus kedua sebagai contoh. Membiarkan$N=5^23= 75$, kemudian $\phi(N) = (5^2 - 5)(3 - 1) = 40$, dan $e=3$adalah eksponen yang dapat diterima. Selanjutnya jika saya menghitung semua$c_i=m_i^3\pmod{75}$ untuk semua $0 < m_i < 75$, Saya melihat bahwa ada 3 set perbedaan $m_i$ nilai-nilai yang memberikan hal yang sama $c_i$ setelah enkripsi:

$c_i = 0, m_i=\{0, 15, 30, 45, 60\}$
$c_i = 50, m_i=\{5, 20, 35, 50, 65\}$
$c_i = 25, m_i=\{10, 25, 40, 55, 70\}$

Memikirkan ini $c_i$ nilai-nilai saya menemukan pola berikut $5^3 \equiv 50\pmod{75}$, $5^32\equiv 25\pmod{75}$, $5^33 \equiv 0\pmod{75}$, $5^34 \equiv 50\pmod{75}$dan seterusnya. Mengingat jelas bahwa:

untuk $m_i = 5(3k_j + 0)\pmod{75}, k_j \geq 0$ kita punya $c_i = 0$
untuk $m_i = 5(3k_j + 1)\pmod{75}, k_j \geq 0$ kita punya $c_i = 50$
untuk $m_i = 5(3k_j + 2)\pmod{75}, k_j \geq 0$ kita punya $c_i = 25$

Dan di situlah saya terjebak. Saya telah mencoba mencari contoh untuk$N = p^s$ dan $N=p^sq^r$dan menemukan pola serupa seperti yang ditunjukkan di atas. Tetapi saya masih memerlukan beberapa petunjuk untuk menggeneralisasi perilaku ini dan membuktikan bahwa enkripsi RSA dengan modulus bebas non-persegi bukanlah permutasi. Saya percaya bahwa harus ada beberapa konsep sederhana yang saya lewatkan, tetapi karena saya tidak terlalu menyukai Teori Bilangan, saya membutuhkan bantuan komunitas.

Hanya untuk klarifikasi. Saya benar-benar baik-baik saja dengan pertimbangan efisiensi dan keamanan$p$ dan $q$menjadi dua bilangan prima yang berbeda. Satu-satunya hal yang saya khawatirkan adalah properti bijection fungsi enkripsi RSA (atau tidak ada, yang terjadi).

Terima kasih sebelumnya.

UPD

@poncho memberikan penjelasan yang jelas tentang adanya beberapa preimages untuk $c = 0$. Tetapi juga bagus untuk menggeneralisasi keberadaan ciphertext lain yang dapat memiliki banyak preimage.

Jawaban

1 poncho Aug 19 2020 at 01:32

Sementara sebagian besar jawaban bermuara pada pertimbangan efisiensi dan keamanan, terdapat satu jawaban yang menyatakan bahwa fungsi enkripsi RSA dengan modulus yang terdiri dari pangkat utama kehilangan sifat bijeksinya, yaitu bukan permutasi lagi. Namun perilaku ini hanya ditampilkan pada contoh tanpa bukti.

Ini agak mudah untuk didemonstrasikan (dengan asumsi $e>1$; dengan$e=1$, itu permutasi, tapi bukan yang sangat menarik).

Nilai $N$ tidak gratis jika ada nilai $p>1, q$ seperti yang $N = p^2q$ (perhatikan itu $q$ mungkin $p$sebagai faktor). Jika demikian, maka pertimbangkan enkripsi kedua nilai tersebut$0$ dan $pq$. Dalam dua kasus, kami memiliki:

$$0^e \equiv 0 \pmod N$$

$$(pq)^e \equiv p^eq^e \equiv p^{2+x}q^{1+y} \pmod N$$

untuk $x = e-2$ dan $y = e-1$. Sekarang, keduanya$x, y \ge 0$, sehingga $p^{2+x}q^{1+y}$ adalah kelipatan dari $p^2q$, dan jadi yang terakhir ini setara dengan $0 \bmod N$