Repository: TheAlgorithms/Java
Pull request #5700 (2024-10-10 12:02:23)

Add Elliptic Curve Cryptography Algorithm
In this PR, I’ve added the Elliptic Curve Cryptography (ECC) algorithm to the project. The ECC class handles key generation, encryption, and decryption using elliptic curve operations. I also included classes for defining elliptic curves and points on those curves, which are essential for performing ECC computations.

Elliptic Curve Cryptography offers several advantages, including stronger security with smaller key sizes compared to other cryptographic systems like RSA. This makes ECC highly efficient in terms of computational performance, memory usage, and bandwidth, which is especially beneficial for mobile devices and environments with limited resources.

Additionally, I’ve written several unit tests to verify the encryption and decryption processes, ensure randomness in the ciphertexts, and check functionality with known values. This implementation aims to provide a simple but effective introduction to ECC for cryptographic purposes.

codecov-commenter: ## [Codecov](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5700?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) Report
Attention: Patch coverage is `94.66667%` with `4 lines` in your changes missing coverage. Please review.
> Project coverage is 59.88%. Comparing base [(`90d20b3`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/90d20b3a43642548ecc55e425517583080a81e2a?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`b10e451`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/b10e451ebd75b959d813292501498566c970da48?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).

| [Files with missing lines](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5700?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) | Patch % | Lines |
|---|---|---|
| [src/main/java/com/thealgorithms/ciphers/ECC.java](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5700?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fcom%2Fthealgorithms%2Fciphers%2FECC.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#diff-c3JjL21haW4vamF2YS9jb20vdGhlYWxnb3JpdGhtcy9jaXBoZXJzL0VDQy5qYXZh) | 94.66% | [2 Missing and 2 partials :warning: ](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5700?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) |

<details><summary>Additional details and impacted files</summary>


```diff
@@             Coverage Diff              @@
##             master    #5700      +/-   ##
============================================
+ Coverage     59.71%   59.88%   +0.16%     
- Complexity     3855     3864       +9     
============================================
  Files           561      562       +1     
  Lines         16017    16092      +75     
  Branches       3073     3078       +5     
============================================
+ Hits           9565     9637      +72     
- Misses         6047     6049       +2     
- Partials        405      406       +1     
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5700?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).


Patch:
diff --git a/src/main/java/com/thealgorithms/ciphers/ECC.java b/src/main/java/com/thealgorithms/ciphers/ECC.java
new file mode 100644
index 00000000..7b1e37f0
--- /dev/null
+++ b/src/main/java/com/thealgorithms/ciphers/ECC.java
@@ -0,0 +1,236 @@
+package com.thealgorithms.ciphers;
+
+import java.math.BigInteger;
+import java.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
+ */
+public class ECC {
+
+    private BigInteger privateKey; // Private key used for decryption
+    private ECPoint publicKey; // Public key used for encryption
+    private EllipticCurve curve; // Elliptic curve used in cryptography
+    private ECPoint basePoint; // Base point G on the elliptic curve
+
+    public ECC(int bits) {
+        generateKeys(bits); // Generates public-private key pair
+    }
+
+    public EllipticCurve getCurve() {
+        return curve; // Returns the elliptic curve
+    }
+
+    public void setCurve(EllipticCurve curve) {
+        this.curve = curve;
+    }
+
+    // Getter and Setter for private key
+    public BigInteger getPrivateKey() {
+        return privateKey;
+    }
+
+    public void setPrivateKey(BigInteger privateKey) {
+        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)
+     */
+    public ECPoint[] encrypt(String message) {
+        BigInteger m = new BigInteger(message.getBytes()); // Convert message to BigInteger
+        SecureRandom r = new SecureRandom(); // Generate random value for k
+        BigInteger k = new BigInteger(curve.getFieldSize(), r); // Generate random scalar k
+
+        // Calculate point r = k * G, where G is the base point
+        ECPoint rPoint = basePoint.multiply(k, curve.getP(), curve.getA());
+
+        // Calculate point s = k * publicKey + encodedMessage
+        ECPoint sPoint = publicKey.multiply(k, curve.getP(), curve.getA()).add(curve.encodeMessage(m), curve.getP(), curve.getA());
+
+        return new ECPoint[] {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
+     */
+    public String decrypt(ECPoint[] encryptedMessage) {
+        ECPoint rPoint = encryptedMessage[0]; // First part of ciphertext
+        ECPoint sPoint = encryptedMessage[1]; // Second part of ciphertext
+
+        // Perform decryption: s - r * privateKey
+        ECPoint decodedMessage = sPoint.subtract(rPoint.multiply(privateKey, curve.getP(), curve.getA()), curve.getP(), curve.getA());
+
+        BigInteger m = curve.decodeMessage(decodedMessage); // Decode the message from ECPoint
+
+        return new String(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
+     */
+    public final void generateKeys(int bits) {
+        SecureRandom r = new SecureRandom();
+        curve = new EllipticCurve(bits); // Initialize a new elliptic curve
+        basePoint = curve.getBasePoint(); // Set the base point G
+
+        // Generate private key as a random BigInteger
+        privateKey = new BigInteger(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.
+     */
+    public static class EllipticCurve {
+        private final BigInteger a; // Coefficient a in the curve equation
+        private final BigInteger b; // Coefficient b in the curve equation
+        private final BigInteger p; // Prime number p, defining the finite field
+        private final ECPoint basePoint; // Base point G on the curve
+
+        // Constructor with explicit parameters for a, b, p, and base point
+        public EllipticCurve(BigInteger a, BigInteger b, BigInteger p, ECPoint basePoint) {
+            this.a = a;
+            this.b = b;
+            this.p = p;
+            this.basePoint = basePoint;
+        }
+
+        // Constructor that randomly generates the curve parameters
+        public EllipticCurve(int bits) {
+            SecureRandom r = new SecureRandom();
+            this.p = BigInteger.probablePrime(bits, r); // Random prime p
+            this.a = new BigInteger(bits, r); // Random coefficient a
+            this.b = new BigInteger(bits, r); // Random coefficient b
+            this.basePoint = new ECPoint(BigInteger.valueOf(4), BigInteger.valueOf(8)); // Fixed base point G
+        }
+
+        public ECPoint getBasePoint() {
+            return basePoint;
+        }
+
+        public BigInteger getP() {
+            return p;
+        }
+
+        public BigInteger getA() {
+            return a;
+        }
+
+        public BigInteger getB() {
+            return b;
+        }
+
+        public int getFieldSize() {
+            return p.bitLength();
+        }
+
+        public ECPoint encodeMessage(BigInteger message) {
+            // Simple encoding of a message as an ECPoint (this is a simplified example)
+            return new ECPoint(message, message);
+        }
+
+        public BigInteger decodeMessage(ECPoint point) {
+            return point.getX(); // Decode the message from ECPoint (simplified)
+        }
+    }
+
+    /**
+     * Class representing a point on the elliptic curve.
+     */
+    public static class ECPoint {
+        private final BigInteger x; // X-coordinate of the point
+        private final BigInteger y; // Y-coordinate of the point
+
+        public ECPoint(BigInteger x, BigInteger y) {
+            this.x = x;
+            this.y = y;
+        }
+
+        public BigInteger getX() {
+            return x;
+        }
+
+        public BigInteger getY() {
+            return y;
+        }
+
+        @Override
+        public String toString() {
+            return "ECPoint(x=" + x.toString() + ", y=" + y.toString() + ")";
+        }
+
+        /**
+         * Add two points on the elliptic curve.
+         */
+        public ECPoint add(ECPoint other, BigInteger p, BigInteger a) {
+            if (this.x.equals(BigInteger.ZERO) && this.y.equals(BigInteger.ZERO)) {
+                return other; // If this point is the identity, return the other point
+            }
+            if (other.x.equals(BigInteger.ZERO) && other.y.equals(BigInteger.ZERO)) {
+                return this; // If the other point is the identity, return this point
+            }
+
+            BigInteger lambda;
+            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);
+            }
+
+            BigInteger xr = lambda.pow(2).subtract(this.x).subtract(other.x).mod(p);
+            BigInteger yr = lambda.multiply(this.x.subtract(xr)).subtract(this.y).mod(p);
+
+            return new ECPoint(xr, yr);
+        }
+
+        /**
+         * Subtract two points on the elliptic curve.
+         */
+        public ECPoint subtract(ECPoint other, BigInteger p, BigInteger a) {
+            ECPoint negOther = new ECPoint(other.x, p.subtract(other.y)); // Negate the Y coordinate
+            return this.add(negOther, p, a); // Add the negated point
+        }
+
+        /**
+         * Multiply a point by a scalar (repeated addition).
+         */
+        public ECPoint multiply(BigInteger k, BigInteger p, BigInteger a) {
+            ECPoint result = new ECPoint(BigInteger.ZERO, BigInteger.ZERO); // Identity point
+            ECPoint addend = 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
+            }
+
+            return result;
+        }
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/ciphers/ECCTest.java b/src/test/java/com/thealgorithms/ciphers/ECCTest.java
new file mode 100644
index 00000000..701f801a
--- /dev/null
+++ b/src/test/java/com/thealgorithms/ciphers/ECCTest.java
@@ -0,0 +1,106 @@
+package com.thealgorithms.ciphers;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertNotEquals;
+
+import java.math.BigInteger;
+import org.junit.jupiter.api.Test;
+
+/**
+ * ECCTest - Unit tests for the ECC (Elliptic Curve Cryptography) implementation.
+ * This class contains various test cases to validate the encryption and decryption functionalities.
+ * It ensures the correctness and randomness of ECC operations.
+ *
+ * @author xuyang
+ */
+public class ECCTest {
+    ECC ecc = new ECC(256); // Generate a 256-bit ECC key pair. Calls generateKeys(bits) to create keys including privateKey and publicKey.
+
+    /**
+     * Test the encryption functionality: convert plaintext to ciphertext and output relevant encryption data.
+     */
+    @Test
+    void testEncrypt() {
+        String textToEncrypt = "Elliptic Curve Cryptography";
+
+        ECC.ECPoint[] cipherText = ecc.encrypt(textToEncrypt); // Perform encryption
+
+        // Output private key information
+        System.out.println("Private Key: " + ecc.getPrivateKey());
+
+        // Output elliptic curve parameters
+        ECC.EllipticCurve curve = ecc.getCurve();
+        System.out.println("Elliptic Curve Parameters:");
+        System.out.println("a: " + curve.getA());
+        System.out.println("b: " + curve.getB());
+        System.out.println("p: " + curve.getP());
+        System.out.println("Base Point G: " + curve.getBasePoint());
+
+        // Verify that the ciphertext is not empty
+        assertEquals(cipherText.length, 2); // Check if the ciphertext contains two points (R and S)
+
+        // Output the encrypted coordinate points
+        System.out.println("Encrypted Points:");
+        for (ECC.ECPoint point : cipherText) {
+            System.out.println(point); // Calls ECPoint's toString() method
+        }
+    }
+
+    /**
+     * Test the decryption functionality: convert ciphertext back to plaintext using known private key and elliptic curve parameters.
+     */
+    @Test
+    void testDecryptWithKnownValues() {
+        // 1. Define the known private key
+        BigInteger knownPrivateKey = new BigInteger("28635978664199231399690075483195602260051035216440375973817268759912070302603");
+
+        // 2. Define the known elliptic curve parameters
+        BigInteger a = new BigInteger("64505295837372135469230827475895976532873592609649950000895066186842236488761"); // Replace with known a value
+        BigInteger b = new BigInteger("89111668838830965251111555638616364203833415376750835901427122343021749874324"); // Replace with known b value
+        BigInteger p = new BigInteger("107276428198310591598877737561885175918069075479103276920057092968372930219921"); // Replace with known p value
+        ECC.ECPoint basePoint = new ECC.ECPoint(new BigInteger("4"), new BigInteger("8")); // Replace with known base point coordinates
+
+        // 3. Create the elliptic curve object
+        ECC.EllipticCurve curve = new ECC.EllipticCurve(a, b, p, basePoint);
+
+        // 4. Define the known ciphertext containing two ECPoints (R, S)
+        ECC.ECPoint rPoint = new ECC.ECPoint(new BigInteger("103077584019003058745849614420912636617007257617156724481937620119667345237687"), new BigInteger("68193862907937248121971710522760893811582068323088661566426323952783362061817"));
+        ECC.ECPoint sPoint = new ECC.ECPoint(new BigInteger("31932232426664380635434632300383525435115368414929679432313910646436992147798"), new BigInteger("77299754382292904069123203569944908076819220797512755280123348910207308129766"));
+        ECC.ECPoint[] cipherText = new ECC.ECPoint[] {rPoint, sPoint};
+
+        // 5. Create an ECC instance and set the private key and curve parameters
+        ecc.setPrivateKey(knownPrivateKey); // Use setter method to set the private key
+        ecc.setCurve(curve); // Use setter method to set the elliptic curve
+
+        // 6. Decrypt the known ciphertext
+        String decryptedMessage = ecc.decrypt(cipherText);
+
+        // 7. Compare the decrypted plaintext with the expected value
+        String expectedMessage = "Elliptic Curve Cryptography"; // Expected plaintext
+        assertEquals(expectedMessage, decryptedMessage);
+    }
+
+    /**
+     * Test that encrypting the same plaintext with ECC produces different ciphertexts.
+     */
+    @Test
+    void testCipherTextRandomness() {
+        String message = "Elliptic Curve Cryptography";
+
+        ECC.ECPoint[] cipherText1 = ecc.encrypt(message);
+        ECC.ECPoint[] cipherText2 = ecc.encrypt(message);
+
+        assertNotEquals(cipherText1, cipherText2); // Ensure that the two ciphertexts are different
+    }
+
+    /**
+     * Test the entire ECC encryption and decryption process.
+     */
+    @Test
+    void testECCEncryptionAndDecryption() {
+        String textToEncrypt = "Elliptic Curve Cryptography";
+        ECC.ECPoint[] cipherText = ecc.encrypt(textToEncrypt);
+        String decryptedText = ecc.decrypt(cipherText);
+        assertEquals(textToEncrypt, decryptedText); // Verify that the decrypted text matches the original text
+    }
+}