LUC Cryptosystem Pada tahun 1993, Peter J. Smith dan Michael J. Lennon mengajukan sebuah varian dari RSA, yang disebut dengan LUC. Sistem ini berbasis pada rangkaian Lucas. Rangkaian ini didapatkan dari persamaan kuadarat x2-ax+b=0, dimana a,b merupakan integer ≠0. Dari persamaan tersebut, dapat kita hitung nilai diskriminan dengan rumus D=a2-4b. Kemudian dihitung kedua akar dari persamaan, yaitu:
α=
a+ D 2
β=
a− D 2
Sesuai dengan sifat yang ada pada persamaan kuadrat, dapat dinyatakan bahwa:
α +β =a
α −β = D αβ = b Selanjutnya, kita definisikan Rangkaian (Uk) dan (Vk)
U k ( a , b) =
αk − βk α −β
Vk ( a, b) = α k + β k
Dari persamaan di atas kita dapatkan, U0(a,b)=0, U1(a,b)=1, sedangkan V0(a,b)=2, V1(a,b)=a. Sedangkan untuk k≥2, dapat dirumuskan Uk(a,b) = aUk-1-bUk-2…… (1) Vk(a,b) = aVk-1-bVk-2…… (2) Rangkaian U(a,b)=(Uk(a,b))k≥0 dan V(a,b)=(Vk(a,b))k≥0 disebut dengan rangkaian Lucas. Berikut ini dijelaskan pembuktian persamaan (1) dan (2) (1) Uk(a,b )=aUk-1-bUk-2
α k − β k (α + β )(α k −1 − β k −1 ) (α k −2 − β k −2 ) = − αβ α −β α −β α −β ⇒ α k − β k = (α + β )(α k −1 − β k −1 ) − αβ (α k − 2 − β k − 2 ) ⇒ α k − β k = α k + βα k −1 − αβ k −1 − β k − α k −1 β + αβ k −1
⇒αk − βk =αk −βk terbukti (2) Vk(a,b)=aVk-1-bVk-2 ⇒ α k + β k = (α + β )(α k −1 − β k −1 ) − αβ (α k − 2 − β k − 2 ) ⇒ α k + β k = α k + βα k −1 + αβ k −1 + β k − βα k −1 − αβ k −1 ⇒αk + βk =αk + βk terbukti
Setelah didapatkan rangkaian lucas, selanjutnya kita masuki tahap penyandian. Anggap bahwa Bob mengirim sebuah teks sandi kepada Alice. Tahap penyandian terdiri dari: 1. Pembangkitan Kunci: Alice mengirimkan kunci public nya (e,N), yang memenuhi N=pq, dimana p,q € prima, ed ≡ 1(mod( p 2 − 1)(q 2 − 1)), dengan gcd(e, ( p 2 − 1)(q 2 − 1)) = 1 2. Enkripsi: Bob mengenkrip pesan M dengan ketentuan 1 < M < N-1 dengan gcd (M,N) = 1. Selanjutnya, mengenkripsinya dengan rumus
C ≡ Ve ( M ,1)(mod N ) 3. Dekripsi Alice melakukan dekripsi dengan rumus
M ≡ Vd (C ,1)(mod N ) Contoh soal: Bob akan mengirim pesan M kepada Alice. Untuk melakukan hal itu, Alice harus mengirimkan public key nya (e, N) kepada Bob. Berikut ini, didapatkan proses pembangkitan kunci, enkripsi, dan dekripsi dengan menggunakan Mapple 12.
Pembangkitan Kunci p = 101, q = 53 dan e = 7; N= p.q = 5353;
S(n) = (p2-1)(q2-1) = 28641600 d = 24549943 merupakan invers dari e mod S(n)
Enkripsi M = 47 C ≡ V7 (47,1) mod 5353 C = 3654
Dekripsi C = 3654 M ≡ V24549943 (3654,1) mod 5353 M = 47