ECC.java

packagecom.thealgorithms.ciphers;

importjava.math.BigInteger;
importjava.security.SecureRandom;

/**
 * ECC - Elliptic Curve Cryptography
 * Elliptic Curve Cryptography is a public-key cryptography method that uses the algebraic structure of
 * elliptic curves over finite fields. ECC provides a higher level of security with smaller key sizes compared
 * to other public-key methods like RSA, making it particularly suitable for environments where computational
 * resources are limited, such as mobile devices and embedded systems.
 *
 * This class implements elliptic curve cryptography, providing encryption and decryption
 * functionalities based on public and private key pairs.
 *
 * @author xuyang
 */
publicclassECC {

privateBigIntegerprivateKey; // Private key used for decryption
privateECPointpublicKey; // Public key used for encryption
privateEllipticCurvecurve; // Elliptic curve used in cryptography
privateECPointbasePoint; // Base point G on the elliptic curve

publicECC(intbits) {
generateKeys(bits); // Generates public-private key pair
 }

publicEllipticCurvegetCurve() {
returncurve; // Returns the elliptic curve
 }

publicvoidsetCurve(EllipticCurvecurve) {
this.curve = curve;
 }

// Getter and Setter for private key
publicBigIntegergetPrivateKey() {
returnprivateKey;
 }

publicvoidsetPrivateKey(BigIntegerprivateKey) {
this.privateKey = privateKey;
 }

/**
 * Encrypts the message using the public key.
 * The message is transformed into an ECPoint and encrypted with elliptic curve operations.
 *
 * @param message The plain message to be encrypted
 * @return The encrypted message as an array of ECPoints (R, S)
 */
publicECPoint[] encrypt(Stringmessage) {
BigIntegerm = newBigInteger(message.getBytes()); // Convert message to BigInteger
SecureRandomr = newSecureRandom(); // Generate random value for k
BigIntegerk = newBigInteger(curve.getFieldSize(), r); // Generate random scalar k

// Calculate point r = k * G, where G is the base point
ECPointrPoint = basePoint.multiply(k, curve.getP(), curve.getA());

// Calculate point s = k * publicKey + encodedMessage
ECPointsPoint = publicKey.multiply(k, curve.getP(), curve.getA()).add(curve.encodeMessage(m), curve.getP(), curve.getA());

returnnewECPoint[] {rPoint, sPoint}; // Return encrypted message as two ECPoints
 }

/**
 * Decrypts the encrypted message using the private key.
 * The decryption process is the reverse of encryption, recovering the original message.
 *
 * @param encryptedMessage The encrypted message as an array of ECPoints (R, S)
 * @return The decrypted plain message as a String
 */
publicStringdecrypt(ECPoint[] encryptedMessage) {
ECPointrPoint = encryptedMessage[0]; // First part of ciphertext
ECPointsPoint = encryptedMessage[1]; // Second part of ciphertext

// Perform decryption: s - r * privateKey
ECPointdecodedMessage = sPoint.subtract(rPoint.multiply(privateKey, curve.getP(), curve.getA()), curve.getP(), curve.getA());

BigIntegerm = curve.decodeMessage(decodedMessage); // Decode the message from ECPoint

returnnewString(m.toByteArray()); // Convert BigInteger back to String
 }

/**
 * Generates a new public-private key pair for encryption and decryption.
 *
 * @param bits The size (in bits) of the keys to generate
 */
publicfinalvoidgenerateKeys(intbits) {
SecureRandomr = newSecureRandom();
curve = newEllipticCurve(bits); // Initialize a new elliptic curve
basePoint = curve.getBasePoint(); // Set the base point G

// Generate private key as a random BigInteger
privateKey = newBigInteger(bits, r);

// Generate public key as the point publicKey = privateKey * G
publicKey = basePoint.multiply(privateKey, curve.getP(), curve.getA());
 }

/**
 * Class representing an elliptic curve with the form y^2 = x^3 + ax + b.
 */
publicstaticclassEllipticCurve {
privatefinalBigIntegera; // Coefficient a in the curve equation
privatefinalBigIntegerb; // Coefficient b in the curve equation
privatefinalBigIntegerp; // Prime number p, defining the finite field
privatefinalECPointbasePoint; // Base point G on the curve

// Constructor with explicit parameters for a, b, p, and base point
publicEllipticCurve(BigIntegera, BigIntegerb, BigIntegerp, ECPointbasePoint) {
this.a = a;
this.b = b;
this.p = p;
this.basePoint = basePoint;
 }

// Constructor that randomly generates the curve parameters
publicEllipticCurve(intbits) {
SecureRandomr = newSecureRandom();
this.p = BigInteger.probablePrime(bits, r); // Random prime p
this.a = newBigInteger(bits, r); // Random coefficient a
this.b = newBigInteger(bits, r); // Random coefficient b
this.basePoint = newECPoint(BigInteger.valueOf(4), BigInteger.valueOf(8)); // Fixed base point G
 }

publicECPointgetBasePoint() {
returnbasePoint;
 }

publicBigIntegergetP() {
returnp;
 }

publicBigIntegergetA() {
returna;
 }

publicBigIntegergetB() {
returnb;
 }

publicintgetFieldSize() {
returnp.bitLength();
 }

publicECPointencodeMessage(BigIntegermessage) {
// Simple encoding of a message as an ECPoint (this is a simplified example)
returnnewECPoint(message, message);
 }

publicBigIntegerdecodeMessage(ECPointpoint) {
returnpoint.getX(); // Decode the message from ECPoint (simplified)
 }
 }

/**
 * Class representing a point on the elliptic curve.
 */
publicstaticclassECPoint {
privatefinalBigIntegerx; // X-coordinate of the point
privatefinalBigIntegery; // Y-coordinate of the point

publicECPoint(BigIntegerx, BigIntegery) {
this.x = x;
this.y = y;
 }

publicBigIntegergetX() {
returnx;
 }

publicBigIntegergetY() {
returny;
 }

@Override
publicStringtoString() {
return"ECPoint(x=" + x.toString() + ", y=" + y.toString() + ")";
 }

/**
 * Add two points on the elliptic curve.
 */
publicECPointadd(ECPointother, BigIntegerp, BigIntegera) {
if (this.x.equals(BigInteger.ZERO) && this.y.equals(BigInteger.ZERO)) {
returnother; // If this point is the identity, return the other point
 }
if (other.x.equals(BigInteger.ZERO) && other.y.equals(BigInteger.ZERO)) {
returnthis; // If the other point is the identity, return this point
 }

BigIntegerlambda;
if (this.equals(other)) {
// Special case: point doubling
lambda = this.x.pow(2).multiply(BigInteger.valueOf(3)).add(a).multiply(this.y.multiply(BigInteger.valueOf(2)).modInverse(p)).mod(p);
 } else {
// General case: adding two different points
lambda = other.y.subtract(this.y).multiply(other.x.subtract(this.x).modInverse(p)).mod(p);
 }

BigIntegerxr = lambda.pow(2).subtract(this.x).subtract(other.x).mod(p);
BigIntegeryr = lambda.multiply(this.x.subtract(xr)).subtract(this.y).mod(p);

returnnewECPoint(xr, yr);
 }

/**
 * Subtract two points on the elliptic curve.
 */
publicECPointsubtract(ECPointother, BigIntegerp, BigIntegera) {
ECPointnegOther = newECPoint(other.x, p.subtract(other.y)); // Negate the Y coordinate
returnthis.add(negOther, p, a); // Add the negated point
 }

/**
 * Multiply a point by a scalar (repeated addition).
 */
publicECPointmultiply(BigIntegerk, BigIntegerp, BigIntegera) {
ECPointresult = newECPoint(BigInteger.ZERO, BigInteger.ZERO); // Identity point
ECPointaddend = this;

while (k.signum() > 0) {
if (k.testBit(0)) {
result = result.add(addend, p, a); // Add the current point
 }
addend = addend.add(addend, p, a); // Double the point
k = k.shiftRight(1); // Divide k by 2
 }

returnresult;
 }
 }
}