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

Question

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: [1] Was that the right way to encode the message? [2] 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!!!

Answer 1

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}$