Asymmetric Encryption (Criptografia Assimétrica)

Asymmetric encryption, also known as public-key cryptography, uses a pair of mathematically related keys: a public key that can be shared openly and a private key that must remain secret. This solves the fundamental problem of secure communication without pre-existing shared secrets.

Mathematical Foundations

The Discrete Logarithm Problem

Given a prime $p$, a generator $g$, and value $y = g^x \mod p$, finding $x$ given $(p, g, y)$ is computationally difficult for large values of $p$. This forms the basis of: - Diffie-Hellman Key Exchange - ElGamal Encryption

The Integer Factorization Problem

Given a large composite number $n = p \times q$ (where $p, q$ are primes), finding $p$ and $q$ is difficult. This forms the basis of: - RSA Encryption

Elliptic Curve Discrete Logarithm Problem

Finding $k$ given points $P$ and $Q = kP$ on an elliptic curve is computationally hard, even for relatively small key sizes. This enables: - ECC (Elliptic Curve Cryptography) - smaller keys with equivalent security to RSA

RSA Encryption (Criptografia RSA)

RSA is the most widely used asymmetric encryption algorithm, based on the difficulty of factoring large integers.

Mathematical Foundation

Given: 1. Two large prime numbers $p$ and $q$ (typically 1024 bits each for a 2048-bit key) 2. Modulus $n = p \times q$ 3. Euler's totient function $\phi(n) = (p-1)(q-1)$ 4. Public exponent $e$ (typically 65537, coprime to $\phi(n)$) 5. Private exponent $d$ such that $ed \equiv 1 \mod \phi(n)$

Encryption: $C = M^e \mod n$
Decryption: $M = C^d \mod n$

Where: - $M$ is the plaintext message (must be less than $n$) - $C$ is the ciphertext - All operations are modular arithmetic

Key Generation Process

def generate_rsa_keypair(bits=2048):
    # Generate two large prime numbers
    p = get_large_prime(bits // 2)
    q = get_large_prime(bits // 2)

    # Compute modulus and totient
    n = p * q
    phi_n = (p - 1) * (q - 1)

    # Choose public exponent e (typically 65537)
    e = 65537

    # Verify gcd(e, phi(n)) == 1
    assert math.gcd(e, phi_n) == 1

    # Compute private exponent d
    d = modInverse(e, phi_n)

    return {
        'n': n,
        'e': e,
        'd': d,
        'p': p,
        'q': q
    }

Java Implementation

import java.math.BigInteger;
import java.security.*;
import java.util.Base64;

public class RSAEncryption {

    private static final int KEY_SIZE = 2048;

    /**
     * Generates a new RSA key pair.
     */
    public static KeyPair generateKeyPair() throws Exception {
        KeyPairGenerator keyGen = KeyPairGenerator.getInstance("RSA");
        keyGen.initialize(KEY_SIZE);
        return keyGen.generateKeyPair();
    }

    /**
     * Encrypts data using the recipient's public key.
     */
    public static String encrypt(String plaintext, PublicKey publicKey) throws Exception {
        // For RSA encryption of large messages, use hybrid approach:
        // 1. Generate random symmetric key
        // 2. Encrypt message with symmetric key (AES)
        // 3. Encrypt symmetric key with recipient's public key (RSA)

        // Simple example for small messages only:
        javax.crypto.Cipher cipher = javax.crypto.Cipher.getInstance("RSA/ECB/OAEPWithSHA-256AndMGF1Padding");
        cipher.init(javax.crypto.Cipher.ENCRYPT_MODE, publicKey);

        byte[] encryptedBytes = cipher.doFinal(plaintext.getBytes());
        return Base64.getEncoder().encodeToString(encryptedBytes);
    }

    /**
     * Decrypts data using the private key.
     */
    public static String decrypt(String encodedCiphertext, PrivateKey privateKey) throws Exception {
        byte[] ciphertext = Base64.getDecoder().decode(encodedCiphertext);

        javax.crypto.Cipher cipher = javax.crypto.Cipher.getInstance("RSA/ECB/OAEPWithSHA-256AndMGF1Padding");
        cipher.init(javax.crypto.Cipher.DECRYPT_MODE, privateKey);

        byte[] decryptedBytes = cipher.doFinal(ciphertext);
        return new String(decryptedBytes);
    }

    /**
     * Manual RSA encryption/decryption (for educational purposes only).
     */
    public static String manualEncrypt(String message, BigInteger n, int e) throws Exception {
        // Convert message to number
        byte[] messageBytes = message.getBytes();
        BigInteger m = new BigInteger(1, messageBytes);

        // Encrypt: C = M^e mod n
        BigInteger c = m.modPow(e, n);

        // Convert back to string (base64 for readability)
        return Base64.getEncoder().encodeToString(c.toByteArray());
    }

    public static void main(String[] args) throws Exception {
        // Generate key pair
        KeyPair keyPair = generateKeyPair();
        PublicKey publicKey = keyPair.getPublic();
        PrivateKey privateKey = keyPair.getPrivate();

        String message = "Secret message for RSA encryption";

        System.out.println("Original message: " + message);

        // Encrypt with public key
        String encrypted = encrypt(message, publicKey);
        System.out.println("Encrypted (Base64): " + encrypted);

        // Decrypt with private key
        String decrypted = decrypt(encrypted, privateKey);
        System.out.println("Decrypted: " + decrypted);
    }
}

RSA Key Sizes and Security

Key Size	Estimated Security	Breaking Time (estimated)	Recommendation
1024 bits	~80 bits	Years with cluster	Deprecated
2048 bits	~112 bits	Centuries	Minimum
3072 bits	~128 bits	Millennia	Recommended
4096 bits	~152 bits	Extremely long	High security

Elliptic Curve Cryptography (ECC)

Elliptic Curve Cryptography provides equivalent security to RSA with much smaller key sizes, making it ideal for bandwidth-constrained environments.

Mathematical Foundation

An elliptic curve over a finite field is defined by the equation: $$y^2 = x^3 + ax + b \mod p$$

The elliptic curve discrete logarithm problem (ECDLP): Given points $P$ and $Q = kP$, finding $k$ is computationally infeasible.

Key Sizes Comparison

Security Level	RSA Key Size	ECC Key Size
128-bit	3072 bits	256 bits
192-bit	7680 bits	384 bits
256-bit	15360 bits	512 bits

ECDSA (Elliptic Curve Digital Signature Algorithm)

ECDSA is used for digital signatures and provides the same security as RSA with smaller keys.

import java.security.*;
import org.bouncycastle.jce.provider.BouncyCastleProvider;

public class ECDSASignature {

    static {
        Security.addProvider(new BouncyCastleProvider());
    }

    /**
     * Generates an ECC key pair (P-256 curve).
     */
    public static KeyPair generateKeyPair() throws Exception {
        KeyPairGenerator keyGen = KeyPairGenerator.getInstance("EC", "BC");
        keyGen.initialize(256);
        return keyGen.generateKeyPair();
    }

    /**
     * Signs data using ECDSA.
     */
    public static byte[] signData(byte[] message, PrivateKey privateKey) throws Exception {
        Signature signature = Signature.getInstance("SHA256withECDSA", "BC");
        signature.initSign(privateKey);
        signature.update(message);
        return signature.sign();
    }

    /**
     * Verifies an ECDSA signature.
     */
    public static boolean verifySignature(byte[] message, byte[] signatureBytes, PublicKey publicKey) throws Exception {
        Signature signature = Signature.getInstance("SHA256withECDSA", "BC");
        signature.initVerify(publicKey);
        signature.update(message);
        return signature.verify(signatureBytes);
    }

    public static void main(String[] args) throws Exception {
        KeyPair keyPair = generateKeyPair();
        PublicKey publicKey = keyPair.getPublic();
        PrivateKey privateKey = keyPair.getPrivate();

        byte[] message = "Message to sign".getBytes();

        // Sign the message
        byte[] signature = signData(message, privateKey);
        System.out.println("Signature length: " + signature.length + " bytes");

        // Verify the signature
        boolean isValid = verifySignature(message, signature, publicKey);
        System.out.println("Signature valid: " + isValid);
    }
}

ECDH (Elliptic Curve Diffie-Hellman) Key Exchange

ECDH allows two parties to establish a shared secret using elliptic curve cryptography.

import java.math.BigInteger;
import org.bouncycastle.jce.provider.BouncyCastleProvider;

public class ECKeyExchange {

    static {
        Security.addProvider(new BouncyCastleProvider());
    }

    /**
     * Generates an ECDH key pair.
     */
    public static KeyPair generateECDHKeyPair() throws Exception {
        KeyPairGenerator keyGen = KeyPairGenerator.getInstance("EC", "BC");
        keyGen.initialize(256);
        return keyGen.generateKeyPair();
    }

    /**
     * Computes shared secret using peer's public key.
     */
    public static byte[] computeSharedSecret(PublicKey theirPublicKey, PrivateKey myPrivateKey) throws Exception {
        // Use ECDH to derive shared secret
        KeyAgreement agreement = new KeyAgreement(KeyAgreement.getInstance("ECDH", "BC"));
        agreement.init(myPrivateKey);
        agreement.doPhase(theirPublicKey, true);

        SecretKey sharedSecret = agreement.generateSecret();
        return sharedSecret.getEncoded();
    }

    public static void main(String[] args) throws Exception {
        // Alice generates key pair
        KeyPair aliceKeys = generateECDHKeyPair();
        PublicKey alicePublic = aliceKeys.getPublic();
        PrivateKey alicePrivate = aliceKeys.getPrivate();

        // Bob generates key pair
        KeyPair bobKeys = generateECDHKeyPair();
        PublicKey bobPublic = bobKeys.getPublic();
        PrivateKey bobPrivate = bobKeys.getPrivate();

        // Alice computes shared secret using Bob's public key
        byte[] aliceSecret = computeSharedSecret(bobPublic, alicePrivate);

        // Bob computes shared secret using Alice's public key
        byte[] bobSecret = computeSharedSecret(alicePublic, bobPrivate);

        System.out.println("Alice and Bob have the same shared secret: " + 
            java.util.Arrays.equals(aliceSecret, bobSecret));
    }
}

ElGamal Encryption

ElGamal is based on the discrete logarithm problem and provides probabilistic encryption.

Mathematical Foundation

Given: - A large prime $p$ - A generator $g$ of $\mathbb{Z}_p^*$ - Public key $(p, g, y)$ where $y = g^x \mod p$ (private key is $x$)

Encryption: To encrypt message $m$: 1. Choose random $k$ 2. Compute $c_1 = g^k \mod p$ 3. Compute $c_2 = m \cdot y^k \mod p$ 4. Ciphertext: $(c_1, c_2)$

Decryption: $$m = c_2 \cdot (c_1^x)^{-1} \mod p$$

Java Implementation

import java.math.BigInteger;
import java.security.SecureRandom;

public class ElGamalEncryption {

    // Standard parameters (RFC 3526)
    private static final BigInteger P = new BigInteger("FFFFFFFFFFFFFFFFC90FDAA2" +
            "2168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B139B22514A087" +
            "98E3404DDEF9519B3CD3A431B302B026038C13ACFFFFFFFBCFC6EE1BBC7FF59" +
            "B88BB9BCB09CBECECDD4EBA3EDBD4547B9280CD73CDA250F164C406CBBA290" +
            "5F47E52BDF9D8EFF2A30E1F7BB4CC89B68F15D42A58ED30ABDDA62FFCF4F90" +
            "3EBC965FFC9BFD859AC479CA81E99A3ED9B6D1FE609731A", 16);

    private static final BigInteger G = new BigInteger("2");

    /**
     * Generates an ElGamal key pair.
     */
    public static KeyPair generateKeyPair() {
        SecureRandom random = new SecureRandom();

        // Generate private key (random in range [3, P-2])
        byte[] privateKeyBytes = new byte[128];
        do {
            random.nextBytes(privateKeyBytes);
        } while (new BigInteger(1, privateKeyBytes).compareTo(P.subtract(BigInteger.ONE)) >= 0 || 
                 new BigInteger(1, privateKeyBytes).compareTo(BigInteger.valueOf(2)) <= 0);

        BigInteger x = new BigInteger(1, privateKeyBytes);

        // Compute public key: y = g^x mod p
        BigInteger y = G.modPow(x, P);

        return new KeyPair(y, x);
    }

    /**
     * Encrypts a message using ElGamal.
     */
    public static byte[] encrypt(BigInteger publicKeyY, BigInteger message, BigInteger theirPublicKey) {
        SecureRandom random = new SecureRandom();

        // Choose random k
        byte[] kBytes = new byte[128];
        random.nextBytes(kBytes);
        BigInteger k = new BigInteger(1, kBytes);

        // Compute c1 = g^k mod p
        BigInteger c1 = G.modPow(k, P);

        // Compute c2 = m * y^k mod p
        BigInteger cy = publicKeyY.modPow(k, P);
        BigInteger c2 = message.multiply(cy).mod(P);

        return new byte[0]; // Simplified - actual implementation would serialize properly
    }

    /**
     * Decrypts an ElGamal ciphertext.
     */
    public static BigInteger decrypt(BigInteger c1, BigInteger c2, PrivateKey privateKeyX) {
        // Compute shared secret: s = c1^x mod p
        BigInteger s = c1.modPow(privateKeyX, P);

        // Decrypt: m = c2 * s^-1 mod p
        BigInteger inverseS = s.modInverse(P);
        return c2.multiply(inverseS).mod(P);
    }
}

Security Considerations

Best Practices for Asymmetric Encryption

1. Use adequate key sizes: RSA 2048+ or ECC P-256 minimum
2. Prefer authenticated encryption: Use OAEP padding for RSA, not PKCS#1 v1.5
3. Avoid raw algorithms: Always use proper modes (RSA-OAEP, ECDSA)
4. Use hybrid encryption: Encrypt data with AES, encrypt key with RSA/ECC
5. Implement certificate validation: Verify certificates in TLS connections

Common Vulnerabilities

Vulnerability	Description	Mitigation
Small subgroup attacks	Attacker forces use of small subgroups	Validate group order
Timing attacks	Side-channel through timing variations	Use constant-time operations
Padding oracle attacks	Exploit padding validation errors	Use OAEP, not PKCS#1 v1.5

When to Use Asymmetric vs Symmetric Encryption

Scenario	Recommended Approach
Encrypting large files	Hybrid (AES + RSA/ECC for key)
Secure messaging	ECDH for key exchange, AES for data
Digital signatures	ECDSA or RSA-PSS
Key distribution	Diffie-Hellman variants

References

1. RFC 8017: PKCS #1: RSA Cryptography Specifications Version 2.2
2. RFC 6979: Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA)
3. RFC 5480: Elliptic Curve Cryptography Subject Public Key Info
4. Menezes, A. J., van Oorschot, P. C., & Vanstone, S. A. (1996). Handbook of Applied Cryptography. CRC Press.