1
$\begingroup$

The RSA algorithm can be used to generate a permutation.

Given two prime numbers $p$ and $q$, the key length is $n=pq$.

If $a$ is the private key, then $b$ is the public key, where $ab \equiv 1 \pmod {\phi(n)}$.

We define a permutation $\pi : \mathbb Z/n\mathbb Z \to \mathbb Z/n\mathbb Z$, given by $\pi(k) = k^b \pmod n$.

Is anything known about these permutations from a group-theoretic point of view?

$\endgroup$
  • $\begingroup$ The usual terminology is that the key length is the number of bits in $n=pq$, rather than $n=pq$. Usually it is assumed $p\ne q$, ensuring that $\pi$ indeed is a permutation. Assuming that, $a$ is a private key matching public key $b$ if and only if $ab\equiv 1\pmod{\operatorname{LCM}(p-1,q-1)}$; but $ab\equiv 1\pmod{\phi(n)}$ may not hold. $\endgroup$ – fgrieu Sep 20 '16 at 17:26
4
$\begingroup$

If you write $\mathbb Z/n\mathbb Z$ first as $\mathbb Z/p\mathbb Z\times \mathbb Z/q\mathbb Z = \mathbb F_p\times\mathbb F_q$, and then $\mathbb F_p$ as $\mathbb F_p^\times\cup\{0\}$ (and the same for $\mathbb F_q$), then you see (using the discrete logarithm) that taking the $b$-th power in $\mathbb F_p^\times$ corresponds to multiplying by $b$ in the cyclic group $\mathbb Z/(p-1)\mathbb Z$, where $b$ is coprime to $p-1$ by assumption.

If $p-1 = \prod_i p_i^{e_i}$ is the prime power factorization of $p-1$, then you get $\mathbb Z/(p-1)\mathbb Z = \prod_i \mathbb Z/p_i^{e_i}\mathbb Z$ and you have to investigate what multiplication by $b$ (coprime to $p_i$) does to $\mathbb Z/p_i^{e_i}\mathbb Z$.

Writing $\mathbb Z/p_i^{e_i}\mathbb Z = \cup_{j=0}^{e_i} p^{e_i-j}(\mathbb Z/p_i^j\mathbb Z)^\times$ you'll see that you have to determine only the order $o$ of (multiplying by) $b$ in $(\mathbb Z/p_i^{e_i}\mathbb Z)^\times$ (as it gives the order of $b$ in $(\mathbb Z/p_i^j\mathbb Z)^\times$ for all $j\le e_i$ --- slight caution is necessary for $p_i=2$ as only for odd $p_i$ one has $(\mathbb Z/p_i^j\mathbb Z)^\times = (\mathbb Z/p_i\mathbb Z)^\times\times \mathbb Z/p_i^{j-1} \mathbb Z$, whereas $(\mathbb Z/2^j\mathbb Z)^\times = (\mathbb Z/2\mathbb Z)\times \mathbb Z/2^{j-2} \mathbb Z$ for $j>1$). Multiplying with an element of order $o$ in a group of order $g$ gives $\frac{g}{o}$ cycles of length $o$.

Now you have to assemble everything again using either the product structures or disjoint unions.

If you were just interested in the order of the permutation, take just the least common multiple of all group orders at the level of $(\mathbb Z/p_i\mathbb Z)^\times$ and $\mathbb Z/p_i^{e_i-1} \mathbb Z$ (don't forget to do the same for $q$ and beware of $p_i=2$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.