Prouver que la fonction de cryptage RSA avec un module non carré libre n'est pas une permutation

Question

Voici un arrière-plan pour la question en cours. En étudiant le RSA, j'ai posé la question de savoir ce qui se passe si$p$ et $q$impliqués dans le calcul du module ne sont pas réellement des nombres premiers? Il existe déjà un sujet connexe à ce sujet ( pourquoi RSA a-t-il besoin de p et q pour être des nombres premiers? ). Alors que la plupart des réponses se résument à des considérations d'efficacité et de sécurité, il existe une réponse unique qui déclare que la fonction de cryptage RSA avec un module composé de puissances premières perd ses propriétés de bijection, c'est-à-dire qu'il ne s'agit plus d'une permutation. Cependant ce comportement n'est montré qu'à titre d'exemple sans preuve.

Compte tenu de cela, j'ai commencé à rechercher une preuve de la propriété de permutation RSA, et j'ai trouvé une telle preuve ici . Mais encore une fois, il déclare que la preuve ne fonctionne que si$p \ne q$, alors qu'il n'est pas vraiment clair pourquoi ce n'est pas pour $p = q$.

Ensuite, j'ai commencé à le déterrer moi-même. En fait, cela semble assez clair pour$p = q$ cas si $p$est primordial. Puis pour$N = p^2$, nous avons un ensemble de textes en clair $\{m_i\}$ tel que $0 \leq m_i < N$ et $m_i \equiv 0\pmod{p}$, et ayant l'exposant $e > 2$ nous avons aussi $m_i^e \equiv 0\pmod{p^2}$.

Mais je ne sais pas comment généraliser les cas pour $N = p^s, s > 2$; $N=p^sq, s > 1$; $N=p^sq^r, s > 2, r > 2$. Prenons un deuxième cas par exemple. Laisser$N=5^23= 75$, puis $\phi(N) = (5^2 - 5)(3 - 1) = 40$, et $e=3$est un exposant acceptable. Ensuite si je calcule tout$c_i=m_i^3\pmod{75}$ pour tous $0 < m_i < 75$, Je vois qu'il y a 3 ensembles de discinct $m_i$ des valeurs qui donnent la même chose $c_i$ après cryptage:

• $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\}$

Penser à cela $c_i$ valeurs j'ai trouvé le modèle suivant $5^3 \equiv 50\pmod{75}$, $5^32\equiv 25\pmod{75}$, $5^33 \equiv 0\pmod{75}$, $5^34 \equiv 50\pmod{75}$etc. Étant donné qu'il est clair que:

• pour $m_i = 5(3k_j + 0)\pmod{75}, k_j \geq 0$ nous avons $c_i = 0$
• pour $m_i = 5(3k_j + 1)\pmod{75}, k_j \geq 0$ nous avons $c_i = 50$
• pour $m_i = 5(3k_j + 2)\pmod{75}, k_j \geq 0$ nous avons $c_i = 25$

Et c'est là que je suis resté. J'ai essayé d'explorer les exemples de$N = p^s$ et $N=p^sq^r$et ont trouvé des modèles similaires comme indiqué ci-dessus. Mais j'ai encore besoin d'indices pour généraliser ce comportement et prouver que le cryptage RSA avec un module libre non carré n'est pas une permutation. Je pense qu'il devrait y avoir un concept simple qui me manque, mais comme je ne suis pas très intéressé par la théorie des nombres, j'ai besoin de l'aide de la communauté.

Juste pour clarifier. Je suis tout à fait d'accord avec les considérations d'efficacité et de sécurité de$p$ et $q$étant deux prime discincte. La seule chose qui m'inquiète est la propriété de bijection de la fonction de cryptage RSA (ou elle est absente, ce qui est le cas).

Merci d'avance.

UPD

@poncho a donné une explication claire sur l'existence de plusieurs pré-images pour $c = 0$. Mais il est également intéressant de généraliser l'existence d'autres textes chiffrés pouvant avoir plusieurs pré-images.

Answer 1

Alors que la plupart des réponses se résument à des considérations d'efficacité et de sécurité, il existe une réponse unique qui déclare que la fonction de cryptage RSA avec un module composé de puissances premières perd ses propriétés de bijection, c'est-à-dire qu'il ne s'agit plus d'une permutation. Cependant ce comportement n'est montré qu'à titre d'exemple sans preuve.

C'est assez simple à démontrer (en supposant $e>1$; avec$e=1$, c'est une permutation, mais pas très intéressante).

Une valeur $N$ est non carré s'il y a une valeur $p>1, q$ tel que $N = p^2q$ (Notez que $q$ puis-je avoir $p$comme facteur). Si tel est le cas, considérez le chiffrement des deux valeurs$0$ et $pq$. Dans les deux cas, on a:

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

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

pour $x = e-2$ et $y = e-1$. Maintenant, les deux$x, y \ge 0$, et donc $p^{2+x}q^{1+y}$ est un multiple de $p^2q$, et donc ce dernier équivaut à $0 \bmod N$

Puisque ces deux textes clairs distincts correspondent au même texte chiffré 0, le mappage ne peut pas être bijectif.