Ilustrasi Bilangan Prima dengan Kriptografi Menggunakan Python

Ilustrasi Bilangan Prima dengan Kriptografi Menggunakan Python

Catatan Belajar oleh : Reza Ervani bin Asmanu

Kriptografi Menggunakan Python merupakan salah satu cara untuk memudahkan memahami matematika kriptografi

Berikut ini adalah contoh sederhana menggunakan Python untuk mengilustrasikan hubungan antara bilangan prima dan kriptografi. Dalam contoh ini, kita akan menggunakan algoritma RSA, yang melibatkan operasi pada bilangan prima.

import random

def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

def generate_prime():
    while True:
        p = random.randint(100, 1000)  # Anggap batas bilangan prima antara 100 dan 1000
        if is_prime(p):
            return p

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def generate_keypair():
    p = generate_prime()
    q = generate_prime()
    n = p * q
    phi = (p - 1) * (q - 1)

    while True:
        e = random.randint(2, phi)
        if gcd(e, phi) == 1:
            break

    d = pow(e, -1, phi)  # Menggunakan algoritma Extended Euclidean untuk menghitung modulo invers dari e dan phi

    public_key = (n, e)
    private_key = (n, d)

    return public_key, private_key

# Contoh penggunaan
public_key, private_key = generate_keypair()
print("Public Key:", public_key)
print("Private Key:", private_key)

 

Dalam script di atas, kita menggunakan beberapa fungsi untuk menghasilkan kunci RSA yang melibatkan bilangan prima:

• Fungsi `is_prime(n)` digunakan untuk memeriksa apakah suatu bilangan `n` adalah bilangan prima. Fungsi ini melakukan iterasi dari 2 hingga akar kuadrat dari `n` untuk memeriksa apakah ada faktor yang membagi `n`.
• Fungsi `generate_prime()` digunakan untuk menghasilkan bilangan prima acak dalam rentang tertentu. Di sini, kita menggunakan rentang antara 100 dan 1000 sebagai contoh.
• Fungsi `gcd(a, b)` menghitung FPB (faktor persekutuan terbesar) dari dua bilangan `a` dan `b` menggunakan algoritma Euclidean.
• Fungsi `generate_keypair()` menghasilkan kunci publik dan kunci privat RSA. Dalam contoh ini, kita menghasilkan dua bilangan prima acak `p` dan `q`, kemudian menghitung `n = p * q` dan `phi = (p – 1) * (q – 1)`. Kita memilih bilangan `e` acak yang relatif prima dengan `phi` sebagai kunci publik. Kita juga menghitung invers modulo `d` dari `e` dan `phi` menggunakan algoritma Extended Euclidean sebagai kunci privat.
• Pada contoh penggunaan terakhir, kita memanggil `generate_keypair()` untuk menghasilkan kunci publik dan kunci privat, dan kemudian mencetaknya sebagai output.

Perlu dicatat bahwa contoh di atas hanya memberikan gambaran sederhana tentang bagaimana bilangan prima terkait dengan kriptografi menggunakan algoritma RSA. Implementasi sebenarnya dari RSA jauh lebih kompleks dan melibatkan langkah-langkah tambahan seperti padding, enkripsi, dan dekripsi yang tidak ditunjukkan dalam script tersebut.