Teknik RSA ( KRIPTOGRAFI )

1.      Teknik RSA

a).  Menentukan Kunci Publik

}  Misalkana = 47 dan

b = 71 (keduanya prima), makadapatdihitung:

  n= a´b = 3337

  f(n)  = (a – 1)´(b – 1)

            = 46 x 70

            = 3220

}  Pilihkuncipublike = 79 yang relatif prima dengan 3220

b).  Menentukan Kunci Privat

}  Selanjutnyaakandihitungkunciprivatddengankekongruenan:

                        e´dº 1 (mod m) = =>

Denganmencobanilai-nilaik = 1, 2, 3, …, diperolehnilaid yang bulatadalah 1019. Iniadalahkunciprivat (untukdekripsi).

Jadi, diketahui kunci publik (e= 79)
                                            n =  3337

                    Kunci privat    (d = 1019)

Kita coba enkripsi dengan plainteks  :   A N D I   S U L A E M A N

Angka dalam ASCII                      :  657868738385766569776578

Ø  Angka dalam ASCII tersebut pecahmenjadi 3 digit

 m1 =  657                       m5 =  766

 m2 =  868                       m6 =  569

 m3 =  738                       m7 =  776

 m4 =  385                       m8 =  578

Ø  Enkripsi Setiap Blok

C1 =     mod  3337  = 2349                C1 =     mod 3337  =  3064

C1 =     mod  3337  =           2629                C1 =     mod 3337  =  1492

  C1 =     mod  3337  = 2623                C1 =     mod 3337  =   14

  C1 =     mod  3337  =           900                  C1 =     mod 3337  =  855

Chiperteks C =  2349262926239003064149214855

Ø  Dekripsi dengan menggunakankunciprivat d = 1019

 m₁=  2349¹⁰¹⁹mod 3337 = 657

m₂=  2629¹⁰¹⁹mod 3337  = 868

m₂=  mod 3337  =  738

m₂=     mod 3337 =  385

m₂=   mod 3337 =  766

m₂=   mod 3337  =  569

m₂=   mod 3337  =  776

m₂=     mod 3337  =  578

Plainteks M  =   6578 68 738385766569776578

Karakter             A  N  D   I    S  U   L  A  E  M  A  N

Algoritma RSA 

ALGORITMA RSA  adalah sistem sandi yang sangat kokoh untuk menyandi ataupun menterjemahkan sandi  RSA menggunakan operasi pemangkatan. Algoritma RSA dibuat oleh 3 orang peneliti dari MIT (Massachussets Institute of Technology) pada tahun 1976, yaitu: Ron (R)ivest, Adi (S)hamir, dan Leonard (A)dleman.

Keamanan algoritma RSA terletak pada sulitnya memfaktorkan bilangan yang besar menjadi faktor-faktor prima. Pemfaktoran dilakukan untuk memperoleh kunci pribadi. Selama pemfaktoran bilangan besar menjadi faktor-faktor prima belum ditemukan algoritma yang mangkus, maka selama itu pula keamanan algoritma RSA tetap terjamin.

Besaran-besaran yang digunakan pada algoritma RSA:

1.  p dan q bilangan prima                                           (rahasia)

2.  r = p × q                                                                  (tidak rahasia)

3.  f(r) = (p – 1)(q – 1)                                                (rahasia)

4.  PK     (kunci enkripsi)                                            (tidak rahasia)

5.  SK     (kunci dekripsi)                                            (rahasia)

6.  X     (plainteks)                                                       (rahasia)

7.  Y    (cipherteks)                                                      (tidak rahasia)

Algoritma RSA didasarkan pada teorema Euler (lihat bahan kuliah Teori Bilangan Bulat) yang menyatakan bahwa

            a^f(r) º 1 (mod r)                                                                       (1)

yang dalam hal ini,

1.      a harus relatif prima terhadap r

2.      f(r) = r(1 – 1/p₁)(1 – 1/p₂) … (1 – 1/p_n), yang dalam hal ini p₁, p₂, …, p_n adalah faktor prima dari r.

f(r) adalah fungsi yang menentukan berapa banyak dari bilangan-bilangan 1, 2, 3, …, r yang relatif prima terhadap r.

Berdasarkan sifat a^m º b^m (mod r) untuk m bilangan bulat ³ 1, maka persamaan (1) dapat ditulis menjadi 

a ^mf(r) º 1^m (mod r)     

atau

                        a^mf(r) º 1 (mod r)                                                         (2)

Bila a diganti dengan X, maka persamaan (2) menjadi

X^mf(r) º 1 (mod r)                                                         (3)

Berdasarkan sifat ac º bc (mod r), maka bila persamaan (3) dikali dengan X menjadi:

X^{mf(r) + 1} º X (mod r)                                                    (4)

yang dalam hal ini X relatif prima terhadap r.

Misalkan SK dan PK dipilih sedemikian sehingga

SK × PK º 1 (mod f(r))                                               (5)

atau

SK × PK = mf(r) + 1                                                    (6)

Sulihkan (6) ke dalam persamaan (4) menjadi:

X ^{SK × PK} º X (mod r)                                                    (7)

           

Persamaan (7) dapat ditulis kembali menjadi

(X ^PK)^SK º X (mod r)                                                    (8)

yang artinya, perpangkatan X dengan PK diikuti dengan perpangkatan dengan SK menghasilkan kembali X semula.

Berdasarkan persamaan (8), maka enkripsi dan dekripsi dirumuskan sebagai berikut:

E_PK(X) = Y º X^PK mod r                                              (8)

D_SK(Y) = X º Y^SK mod r                                              (9)

                                   

Karena SK × PK = PK × SK, maka enkripsi diikuti dengan dekripsi ekivalen dengan dekripsi diikuti enkripsi:

E_SK(D_SK(X)) = D_SK(E_PK(X)) º X^PK mod r         (10)

Oleh karena X^PK mod r º (X + mr)^PK mod r untuk sembarang bilangan bulat m, maka tiap plainteks X, X + r, X + 2r, …, menghasilkan cipherteks yang sama. Dengan kata lain, transformasinya dari banyak ke satu. Agar transformasinya satu-ke-satu, maka X harus dibatasi dalam himpunan {0, 1, 2, …, r – 1} sehingga enkripsi dan dekripsi tetap benar seperti pada persamaan (8) dan (9).

Prosedur Membuat Pasangan Kunci

1.      Pilih dua buah bilangan prima sembarang, p dan q.

2.      Hitung r = p × q. Sebaiknya p ¹ q, sebab jika p = q maka r = p² sehingga p dapat diperoleh dengan menarik akar pangkat dua dari r.

3.      Hitung f(r) = (p – 1)(q – 1).

4.      Pilih kunci publik, PK, yang relatif prima terhadap f(r).

5.      Bangkitkan kunci rahasia dengan menggunakan persamaan (5), yaitu SK × PK º 1 (mod f(r)).

Perhatikan bahwa SK × PK º 1 (mod f(r)) ekivalen dengan  SK × PK = 1 + mf(r), sehingga SK dapat dihitung dengan

                                                                          (11)

Akan terdapat bilangan bulat m yang menyebabkan  memberikan bilangan bulat SK.

Catatan: PK dan SK dapat dipertukarkan urutan pembangkitannya. Jika langkah 4 diganti dengan “Pilih kunci rahasia, SK, yang …”, maka pada langkah 5 kita menghitung kunci publik dengan rumus yang sama.

ALGORITMA RSA

proses kriptografi pada algoritma RSA terdiri dari 3 tahapan yaitu :

1. Pembangkitan Kunci

Untuk membangkitkan kedua kunci, dipilih dua buah bilangan prima yang sangat besar, p dan q. Untuk mendapatkan keamanan yang maksimum, dipilih dua bilangan p dan q yang

besar. Kemudian dihitung :

n = pq

Kemudian dihitung :

φ = (p-1) (q-1)

Lalu dipilih kunci enkripsi e secara acak, sedemikian sehingga e dan (p-1)(q-1) relatif

prima. Artinya e dan φ tidak memiliki faktor persekutuan bersama. Kemudian dengan

algoritma Euclidean yang diperluas, dihitung kunci dekripsi d, sedemikian sehingga :

ed = 1 mod (p-1)(q-1)

atau

ed – 1 = k (p-1)(q-1)

di mana k merupakan konstanta integer.

Perhatikan bahwa d dan n juga relative prima. Bilangan e dan n merupakan kunci publik,

sedangkan d kunci privat. Dua bilangan prima p dan q tidak diperlukan lagi. Namun p dan q

kadang diperlukan untuk mempercepat perhitungan dekripsi.

2. Proses Enkripsi

Untuk mengenkripsi pesan m, terlebih dahulu pesan dibagi ke dalam blok-blok numerik yang lebih kecil dari n (dengan data biner, dipilih pangkat terbesar dari 2 yang kurang dari n).  Jadi,

jika p dan q bilangan prima 100 digit, maka n akan memiliki sekitar 200 buah digit dari setiap blok pesan m, seharusnya kurang dari 200 digit panjangnya. Pesan yang terenkripsi (c), akan tersusun dari blok-blok (c) yang hampir sama panjangnya.

Rumus enkripsinya adalah:

c = me mod n

3. Proses Dekripsi

Setelah menerima pesan yang sudah terenkripsi maka penerima pesan akan melakukan proses

dekripsi pesan dengan cara :

m = cd mod n

Ø  CONTOH PENGGUNAAN ALGORITMA 

- Misal p = 47  dan

q = 71,2¢ 

N = pq = 3337¢  (p-1)(q-1) = 46 * 70 = 3220¢ 

- Pilih e secara acak misalkan e =79,5¢ 

d = 79^-1 m2326od 3220 = 1019¢ 

- Misal pesan yang akan di kirim :

 m = 688232687966668003 

- Maka nilai m di bagi menjadi 6 blok, yaitu :

 m1 = 688                    m2 = 232                     m3 = 687

m4 = 966                     m5 = 668                     m6 = 003

- Enkripsi blok pertama adalah m^e mod n 688^79 mod 3337 = 1570 = c1 

- Dengan cara yang sama untuk setiap blok maka di peroleh :

c = 1507 2765 2091 2276 2423 158 

- Deskripsi dari c ini adalah  c^d mod n , sehingga

1570^1019 mod 3337 = 688 = m1

2765^1019 mod 3337 = 232 = m1

Contoh Program

#include<iostream.h>

#include<conio.h>

#include<math.h>

 int fnIsPrime(int iNumber)

{

                int iCount;

                iCount=2;

                if(iNumber<2)

                    return 0;

                while(iCount<=(iNumber/2))

                {

                                if(iNumber%iCount==0)

                                    return 0;

                                iCount++;

                }

                return 1;

}

int fnMultiply(int iNum1,int iNum2)

{

              return iNum1*iNum2;

}

int fnFindE(int iNum)

{

                int iCount;

                iCount=2;

                while(iCount<iNum)

                {

                                if(iNum%iCount!=0)

                                    return iCount;

                                iCount++;

                }

                return 0;

}

int fnFindD(int iNum1,int iNum2)

{

                int a1,a2,a3,b1,b2,b3,t1,t2,t3,q;

                a1=1;

                a2=0;

                a3=iNum1;

                b1=0;

                b2=1;

                b3=iNum2;

                while(b3!=1)

                {

                                q=a3/b3;

                                t1=a1-(q*b1);

                                t2=a2-(q*b2);

                                t3=a3-(q*b3);

                                 a1=b1;

                                a2=b2;

                                a3=b3;

                                b1=t1;

                                b2=t2;

                                b3=t3;

                }

                if(b2<0)

                    b2=b2+iNum1;

                return b2;

}

int fnFindText(int iNum1,int iNum2,int iNum3)

{

                int iCount,t;

                iCount=1;

                t=1;

                while(iCount<=iNum2)

                {

                                t=t*iNum1;

                                t=t%iNum3;

                                iCount++;

                }

                return (t%iNum3);

}

void main()

{

                long int p,q,n,d,e,pi,pt,ct;

                clrscr();

                cout<<"-----IMPLEMENTATION OF RSA ALGORITHM-----";

                cout<<endl<<endl<<"Enter a prime number :";

                cin>>p;

                cout<<"Enter another prime number :";

                cin>>q;

                if((fnIsPrime(p))&&(fnIsPrime(q)))

                {

                                n=fnMultiply(p,q);

                                cout<<endl<<"/* Intermediate Catculations...";

                                cout<<endl<<"n :"<<n;

                                pi=fnMultiply(p-1,q-1);

                                cout<<endl<<"pi :"<<pi;

                                e=(fnFindE(pi));

                                cout<<endl<<"e :"<<e;

                                d=fnFindD(pi,e);

                                cout<<endl<<"d :"<<d;

                                cout<<"*/";

                                cout<<endl<<endl<<endl<<"----KEYS----";

                                cout<<endl<<"Public Key : ("<<e<<","<<n<<")";

                                cout<<endl<<"Private Key : ("<<d<<","<<n<<")";

                                cout<<endl<<endl<<endl<<"----ENCRYPTION----"<<endl;

                                cout<<"Enter the plain text : ";

                                cin>>pt;

                                ct=fnFindText(pt,e,n);

                                pt=fnFindText(ct,d,n);

                                cout<<"Cipher Text :"<<ct;         

                }

                else

                {

                              cout<<"Error! Enter two prime numbers!";

                }

                getch();

}