Public Key Scheme decryption.

120 Views Asked by At

You have been sent a message based on the following Public Key Scheme.
1) Bob chooses two large primes $\ p,q $ with $ p \equiv q \equiv 2 \pmod 3$ and computes $ n=pq. $
2) Bob chooses integers $ e,d $ with $ ed \equiv 1 $(mod lcm($p+1,q+1). $ (He could use $ (p+1)(q+1) $ instead of $ lcm(p+1,q+1). $ ) And makes $ n $ and $ e $ public.
3) Alice represents her message as a pair of integers $ (m_{1},m_{2}) \pmod n. $ She regards $ (m_{1},m_{2})$ as a point $M$ on the elliptic curve $E$ given by $y^2 = x^3 + b \pmod n, $ where $ b=m_{2} ^2 -m_{1} ^3 \pmod n$ (she does not need to compute $b$).

4) Alice adds $M$ to itself $e$ times on $E$ to obtain $C=(c_{1} ,c_{2} )= eM$ and sends C to Bob.

5)Bob computes $M=dC$ on $E$ to obtain $M$.

Using the described method, and given you have public key $n=9986899671513153299302129148204573775860428310315984346586760515456471532627966903385948703$, encryption integer $e=141597355687225811174313690501511542123673874802409558365796639534962049206893437498331243$ and your secret decryption integer is $d=2037035976334486086268445688409378161051468395093183943342100330412667269212831842566144003$ decode the message $[7702619106292151978427151476214069077485335286048205301635368880467359865152659693199602473, 4357595334666159972997284171164257443639580965587791255697825733007347880407380846464584605 ].$

1

There are 1 best solutions below

2
On BEST ANSWER

This is actually the Elliptic Curve version of the Koyama, Maurer, Okamoto and Vanstone (KMOV) cryptosystem.

Note that the formulas for the addition law on $E_n (0, b)$ never use the value of $b$. Therefore, Bob nevers need to compute it, but he can compute it if he wants as $b = c^2_2 −c^3_1 \pmod n$ (just like Alice had no need).

What is important in this schema is having an algorithm that implements the idea of repeated doubling and addition for computing the decryption that is given by $dP$, where $P$ is the point of interest on the elliptic curve. You have:

$$d = 2^0 + 2^1 + 2^{150} + 2^{300}$$

This would give:

$$M = dC = 2^0C + 2^1C + 2^{150}C + 2^{300}C$$

At this point, just use your favorite CAS like Magma, SAGE, Maxima, GAP, GP/PARI, ... to do this heavy lifting for the point additions and multiplications. For example, see GP/PARI and an example. It also looks like you are using Magma and it appears to have extensive support for elliptic curves, see Magma Elliptic Curves (look at the Operations on Points - Arithmetic link).

We are given:

n

$ n = 9986899671513153299302129148204573775860428310315984346586760515456471532627966903385948703$

Encryption integer

$e=141597355687225811174313690501511542123673874802409558365796639534962049206893437498331243$

Secret decryption integer

$d=2037035976334486086268445688409378161051468395093183943342100330412667269212831842566144003$

We are asked to decode the message $C = (c_1, c_2)$, where

$C = (c_1, c_2) = (7702619106292151978427151476214069077485335286048205301635368880467359865152659693199602473, 4357595334666159972997284171164257443639580965587791255697825733007347880407380846464584605)$

So, on $E$, we would get:

$M = dC =\\ (1916011819050209140118251805161805, 1905142001200915140919211905062112)$

Note: We should be able to use this result of $M$ with $e$ and generate $C$. Indeed, we get:

$C = eM = (7702619106292151978427151476214069077485335286048205301635368880467359865152659693199602473, 4357595334666159972997284171164257443639580965587791255697825733007347880407380846464584605)$

For the record:

$b = c_2^2 - c_1^3 \pmod n= m_2^2 - m_1^3 \pmod n = 5445330577961766747015463565087337781248624265142396436595877867192503947685106526655274667$