An efficient method based on RSA

Hi there,
In this post I'll show the idea of my master thesis. I'll present a new method based on RSA: One has to choose two big distinct primes $p$,$q$ and compute $n=pq$. The essential difference between RSA and presented algorithm is the fact that there is another need to choose an integer $r$ coprime to $n$. All subsequent calculations will be done in the space of numbers of the form $(a+b\sqrt{r})\pmod{n}$, where $a,b\in\mathbb{Z}_n$ are coprimes to $n$. The idea is based on the following theorem.

Theorem
For any prime $m$ and for an integer $r$ which satisfies $\left(\frac{r}{m}\right)=1$ ($\left(\frac{.}{.}\right)$ is Legendre symbol ) and for any $a$ and $b$ coprimes to $m$, the following equality is true:
$(a+b\sqrt{r})^{m-1}\equiv 1\pmod{m}$.

Proof
To prove it, note that from the definition of Legendre symbol $\left(\frac{r}{m}\right)\equiv r^{\frac{m-1}{2}}\pmod{m}$. Therefore,
$(a+b\sqrt{r})^m\stackrel{(*)}{\equiv} a^m+b^mr^{\frac{m}{2}}\stackrel{(**)}{\equiv} a+br^{\frac{m-1}{2}}r^{\frac{1}{2}}\equiv a+b\sqrt{r}\pmod{m}$,
where (*) follows from the fact that all interior Newton binomial coefficients are divisible by $m$, and (**) follows from the fact that $a^m\equiv a\pmod{m}$ for any $a$ coprime to $m$ by Fermat's little theorem. Divide both sides of the equation by $(a+b\sqrt{r})$ yields $(a+b\sqrt{r})^{m-1}\equiv 1\pmod{m}$, what ends the proof.

By our theorem for all $r$ which satisfies both $(\frac{r}{p})=1$ and $(\frac{r}{q})=1$, for $n=p\cdot q$ we have
$
(a+b\sqrt{r})^{(p-1)(q-1)}\equiv 1\pmod{n},
$
which is analogous to the principal fact of the RSA method.

Keys generation
1. Choose two big distinct primes $p$ and $q$. The best way is to choose two primes with similar length and with the property that numbers $p-1$ and $q-1$ are very hard to factor.
2. Compute $n=pq$
3. Compute $w=\varphi(n)=(p-1)(q-1)$
4. Choose random number $r$ with the property that r is a quadratic residue of both $p$ and $q$
5. Choose random number $e$ with the property that $1<e<w$ and $GCD(e,w)=1$
6. Compute $d=e^{-1}\pmod w$

The public key consists of three integers $k_e=(n,r,e)$ and the private key is $k_d=(n,r,d)$.

Encryption
Alice transmits her public key $k_e=(n,r,e)$ to Bob and keeps the private key secret. Then Bob wishes to send message $M$ to Alice.

He first splits $M$ into blocks with length less than double length of $n$. For every piece he splits it into equally-length two parts $a_i$ and $b_i$, then he combines them into number $m_i=a_i+b_i\sqrt{r}$. Then he computes individual pieces of the ciphertext, i.e. $c_i=(c_{i}^{1},c_{i}^{2})$ corresponding to
$
c_i^1+c_i^2\sqrt{r}\equiv(m_i)^e\pmod{n}.
$
To compute $c_i$ he should use a definition of an integer multiplication in the group, i.e.
$(a+b\sqrt{r})(c+d\sqrt{r})=(ac+bdr)+(ad+bc)\sqrt{r}.$

To compute it quickly he can use the method of exponentiation by squaring adjusted to the definition of the multiplication. Bob then transmits $c=(c_1,c_2,\dots)$ to Alice.

Decryption
Alice can recover $m_i$ from $c_i=(c_i^1,c_i^2)$ by using her private key $k_d=(n,r,d)$ via computing
$m_i=a_i+b_i\sqrt{r}=(c_i^1+c_i^2\sqrt{r})^d\pmod{n}$
Given $a_i$ and $b_i$ for every $i$, Alice can recover the original message $M$ by sticking all parts together.

A working example
1. Choose two distinct primes, such as $p=113$ and~$q=127$.
2. Compute $n=pq$ giving $n=113\cdot 127=14351$.
3. Compute $w$ giving $w=(p-1)(q-1)=14112$.
4. Choose any $r$ that fits both $\left(\frac{r}{p}\right)=1$ and $\left(\frac{r}{q}\right)=1$. $r=11$ has such property.
5. Choose any number $1<e<w$ which is coprime to $w$. Let $e=265$.
6. Compute $d$, the modular multiplicative inverse of $e$ modulo $w$, yielding: $d=e^{-1}\pmod{w}\equiv4633\pmod{w}$

Alice obtained public key $k_e=(14351,11,265)$ and private key $k_d=(14351,11,4633)$, then she published the public key.

For instance, in order to encrypt $a+b\sqrt{r}$, where $a=13$, $b=13275$, Bob calculates
$c_1+c_2\sqrt{r}\equiv(13+13275\sqrt{11})^{265}\pmod{14351}\equiv6466+11144\sqrt{11}$,
so he send $c=(6466,11144)$ to Alice. In order to decrypt $c=(c_1,c_2)$ Alice computes
$m=a+b\sqrt{r}\equiv(6466+11144\sqrt{11})^{4633}\pmod{14351}\equiv13+13275\sqrt{11}$,
yielding a pair $(a=13,b=13275)$.

n_smallest_primitive_root at first glance

Hi all,
I've done the first function for FLINT library, namely n_smallest_primitive_root :)
It assumes that on input we have $n$ equal to $2$ or $4$ or $p^k$ or $2\cdot p^k$ for any odd $p\in\mathbb{P}$ and for any $k\in\mathbb{N}$ and finds the least primitive root $\pmod{n}$.
So as I said in the previous post the function iterates a candidate $g$ for being a primitive root from $2$, but it doesn't check all candidates, it misses integers which are divisible by 4, 9 or 25:
if(g % 4 == 0 || g % 9 == 0 || g % 25 == 0) g++;

I'm not quite sure if the last condition (g % 25) is good for speed improve, because it's rare that function must iterates a candidate to such big values.
I will check it later.

At first function assumes it found a real primitive root:
ok = 1;

but then it checks two conditions. If at least one of them is true, value stored in ok changes to 0. The first condition is, if the $g$ value has a multiplicative order not divisible by $\varphi(n)$:
if(n_powmod(g, phi, n) != 1)

The second condition check assumes that $g$ has a multiplicative order divisible by $\varphi(n)$ and check if it can be lower:
for (i = fac.num-1; i >= 0; i--)
{
   exp = phi / fac.p[i];
   if(n_powmod(g, exp, n) == 1)
   {
      ok = 0;
      break;
   }
}

The break inside the for loop is used to speed up - if one finds that it's not a real primitive root, it's senseless to check other cases.

If the function never went inside the break clause, it reaches the next condition:
if(ok == 1)
   return g;

Now it's time for a test phase.

In $10^{8}$ iteration a test finds the following maximal value of minimal primitive root:
$g=151 \pmod{4419925309802}$

My first post

Hi all,
I've made this blog on purpose of Google Summer of Code 2013 initiative.
I am enthusiast of Number Theory so the project I've chose is to develop the FLINT library.

The first test task for me is to write a simple C program which enables user to find a primitive root $\pmod{n}$, where $n$ is any ulong.

A primitive root $\pmod{n}$ is the element in $Z_n$ which has a multiplicative order equals to Euler's totient of $n$ ( $\varphi(n)$ ) - so the maximal case, which is sometimes not possible case. A primitive root $\pmod{n}$ may exist or not depending on $n$. It exists iff $n$ is a prime, or 2*prime or any power of an odd prime or 2*(any power of an odd prime). If primitive roots exist, there are $\varphi(\varphi(n))$ primitive roots modulo $n$. If you found one of them, say $g$, you can generate others by proper exponentiation of $g \pmod{n}$. In order to obtain remain primitive roots, you should use powers which are not divisible by any divisor of $\varphi(n)$.

There is no general strategy on finding primitive root $\pmod{n}$.
A simple case are Fermat Primes, i.e. prime numbers of the form $F_k=2^{2^k} + 1$ for any integer $k$.
In the case, the set of primitive roots is identical to the set of quadratic non-residues $\pmod{n}$ (elements $x$ of $Z_{F_k}$ which have Jacobi symbol $(\frac{x}{F_k})$ equal to $-1$).

In general, $g$ is a primitive root $\pmod{n}$ iff two following sentences are true:
1. $n$ is of the form: $p$ or $2p$ or any power of an odd prime or 2*(any power of an odd prime).
2. $g^{\frac{\varphi(n)}{d_i}}$ is not equal to $1\pmod{n}$ for all $i$ where $d_i$ is a $i$-th divisor of $\varphi(n)$.

There are two approaches on finding any primitive root modulo $n$:
1. Find the smallest primitive root modulo $n$: Iterate $g$ from $2$ to $n-2$ and check if $g$ is a primitive root modulo $n$. Not every value can be a primitive root. One can omit values which are perfect squares. In order to find the smallest primitive root we can omit each values which are divisible by any squares, i.e. $4,9,25$, etc...
2. Find a random primitive root modulo $n$: get a random $g$ from $2$ to $n-2$ and check if $g$ is a primitive root modulo $n$. Again, one can omit values which are perfect squares.

Let's code!