# Is this the right way to implement ElGamal scheme over Elliptic Curves over prime field? [duplicate]

I'm fairly new to Cryptography, especially elliptic curves in general. I learned to do Point Multiplication, Scalar Multiplication and also programmatically implemented them. But I was trying to do ElGamal scheme because I felt intrigued by the subtlety of it. The problem that haunts me is this: Suppose, I have a generator point G on an Elliptic Curve (say SECP256k1 or any curve) , an integer x, which is the private key of this scheme, and I generate the public key P= [x]G . Then, I encode the message to a single number (e) that will be surely less than p, the prime number of the field (256 bit).

ENCRYPTION : I generate a random number k, less than N, where N, is the order of the curve, and also: R = [k]P . I also choose a point C = [k]G. Then I take the x coordinate of R, and do: (x_coordinate of R*e) modulo p -> this will be the cipher text.

DECRYPTION: I take the chosen point C, multiply it with x (private key) to recover the point R back, then I do : (cipher_text*((x_coordinate of R)^(-1) modulo p))modulo p to recover e , the encoded message, which is then decoded back to plain text !

MY CONCERNS:  Was that the right way to encode the message?  If x_coordinate of R * e was smaller than 256 bits then modulo would output the same x_coordinate of R*e which can be easily factored on a computer, and x_coordinate of R could be recovered !

EDITS: What can be the maximum size of x_coordinate of R * e when taking modulo p ? I understand that it should be less than p, but even when I take blocks of plain text such that Rx*e alone exceeds ( 485 bits)the bit size of p (256 bits) I'm able to recover the encoded message back ! I do not know the reason for this creepy behaviour!!! ? Sorry, I'm fairly new to the math of all this !!! BUT: If x_coordinate of R*e is of the order of 2000 bits I totally loose data !!! Infact I am getting it wrong if thats the case! This is what gives me trouble:

/************************
Code for illustration of
my mathematical problem
******************/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <gmpxx.h>

using namespace std;
mpz_class ModInverse(mpz_class a, mpz_class b)
{
mpz_t inv;
mpz_init(inv);
mpz_invert(inv, a.get_mpz_t(), b.get_mpz_t());
return mpz_class(inv);
}
int main()
{
// Prime used by SECP256k1
mpz_class p=mpz_class("115792089237316195423570985008687907853269984665640564039457584007908834671663");
//Let this be some encoded message ...
mpz_class msg=mpz_class("123115792089237316344566776544467896775567567584007908834671663758400790883");
// Let this be the x coordinate of R
mpz_class x=mpz_class("712164785702978780789493774073370493892893827485075314964804772812648384");

cout<< "Encode Message :  "<< msg <<  endl;
cout << "\nx coordinate of R * msg"<< msg*x << endl;
cout << "Product bit length: " << mpz_class(msg*x).get_str(2).length()<< endl;
// Bit length exceeds modulo bit length
mpz_class cph=(msg*x)%p;
cout << "Cipher : "<< cph<< endl;

cout << "\nDecrypted message : "<<  (cph*ModInverse(x, p))%p<< endl;
if ((cph*ModInverse(x, p))%p == msg){
cout << "    Crypto successfull !!!"<< endl;
}
}


EDIT 2: If (x coordinate of R * e ) is less than p then with sufficient amount of cipher text of that form, can an attacker with some cryptanalysis crack it ??? I'm reading a message in blocks...

Sorry If I'm wrong !!!

Every help will be appreciated!!!

• x_coordinate of R and $e$ are not necessarily prime numbers, you do not factor x_coordinate of R * e. And you do not spcecify how to encode the message. – shumy Nov 22 '19 at 13:34
• @shumy: Thankyou for your reply! I use simple hex encoding!!! – Vivekanand V Nov 22 '19 at 13:39
• @fgrieu Yes I wanted more information, therefore I decided to post a separate question... But I understood the concept only just recently... Sorry :) – Vivekanand V Nov 23 '19 at 12:14

1. It does not matter what encoding scheme you use for the message, as long as it is reversible: you should be able to recover the message from e.

2. Assume you do not know $$e$$ or $$R_x$$ (the x-coordinate of $$R$$). You are given $$e \cdot R_x \mod p$$ For any possible message $$e'$$ that you could guess, there is some integer $$n$$ such that $$e'\cdot n \equiv e \cdot R_x \mod p$$ (exercise: what is this $$n$$?)

If you could determine which of $$e$$ and $$e'$$ was the correct message, then you would be able to tell which of $$n$$ and $$R_x$$ is the correct x-value of the shared secret $$R$$. But we assume that the attacker is not able to distinguish $$R$$ from a random point on the curve (this is the Decisional Diffe Hellman assumption).

Essentially, you do not need to worry about an adversary "factoring" $$R_x \cdot e$$, because in the integers mod $$p$$ there is not a unique way of factoring a number, for exactly the same reason that there is no unique way of factoring into rational numbers: $$6 = 3\cdot 2$$, but it also equals $$4 \cdot \frac{2}{3}$$ or $$95 \cdot \frac{6}{95}$$

• Thankyou very much for your reply ! I'm naive to modular arithmetic... :( I do not know what n is... Is it Modulo inverse of x coordinate over prime p or modulo inverse of e' over p... I tried plugging the values to the equations... but Im wrong !!! – Vivekanand V Nov 22 '19 at 16:38
• $n$ is the resulting $R^{'}_{x}$ if you try to guess $e^{'}$. Even if you guess correct you cannot know that $n = R_{x}$. – shumy Nov 22 '19 at 17:05
• @shumy : Sorry, Im unable to read your answer because javascript is not displaying math correctly ! but can you please see my edits !!! ? – Vivekanand V Nov 22 '19 at 17:22
• Please see my edits!!! – Vivekanand V Nov 22 '19 at 18:02
• In your edit, you are able to recover the message because you know x. An attacker would not. You loose data over 2000 bits because you can only encode ~2047 bits of data as an integer mod a 2048-bit prime. The amount of plaintext (as long as it is small enough to be encoded) is irellevant. – Tjaden Hess Nov 22 '19 at 20:48