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)$.