{Deklarasi nama program, unit, variabel dan tipe data} program algoritma_elgamal; uses crt; var p,a,b,c,k,beta,alfa,x,x1,x2,y,y1,y2,q,ai,bs,u,v,r,d1,mp,t,n:longint; tombol:char; pesan:string; i,pilihan,j,w:integer; m,gamma,delta,d,gm,z:array[1..1000] of longint; f,ar,gr:real; {Fungsi Pengecekan Bilangan Prima} function cekprima(a:longint):integer; var b,c:longint; begin b:=1; repeat b:=b+1; c:=a mod b; until c=0; if a=b then cekprima:=1 else cekprima:=0; end; {Fungsi Pengecekan Bilangan Prima Aman} function cekprimaaman(p:longint):integer; var y:longint; begin if cekprima(p)=1 then begin y:=p-1; y:=y div 2; if cekprima(y)=1 then cekprimaaman:=1; if cekprima(y)=0 then cekprimaaman:=0; end else cekprimaaman:=0; end; {Fungsi Mencari Bilangan Prima Aman} function primaaman:longint; var rand:longint; begin randomize; repeat repeat rand:=random(2000)+128+1; if rand mod 2 = 0 then rand:=rand+1; until cekprima(rand)=1; p:=(2*rand)+1; until cekprima(p)=1; primaaman:=p; end; {Metode Fast Exponentiation} function fastexp(r:longint; s:longint; t:longint):longint; var x,mtemp,atemp:longint; begin atemp:=r; mtemp:=s; x:=1; while mtemp <> 0 do begin while mtemp mod 2 = 0 do begin mtemp:=mtemp div 2; atemp:=(atemp*atemp) mod t; end; mtemp:=mtemp-1; x:=(x*atemp) mod t; end; if x<0 then x:=(x+t) mod t; fastexp:=x; end; {Fungsi Tes Keprimaan Miller-Rabbin} function mrtest(p:longint; t:longint):integer; var x,y,s,m,a,r,j,i:longint; begin mrtest:=1; randomize; x:=p; m:=0; repeat x:=x div 2; m:=m+1; until (x mod 2) <> 0; s:=m; r:=x; for i:=1 to t do begin a:=random(p-3)+2; y:=fastexp(a,r,p) mod p; j:=0; if (y<>1) and (y<>(p-1)) then begin j:=1; while (j<=(s-1)) and (y<>(p-1)) do begin y:=(y*y) mod p; if (y=1) then mrtest:=0; j:=j+1; end; if y <> (p-1) then mrtest:=0; end; end; end; {Fungsi Untuk Menghitung gcd(a,b)} function gcd(a:longint; b:longint):longint; var r:longint; begin if a<0 then a:=-a; if b<0 then b:=-b; while b <> 0 do begin r:=a mod b; a:=b; b:=r; end; gcd:=a; end; {Fungsi Untuk Mengecek Elemen Primitif} function cekprimitif(alfa:longint; p:longint):integer; var b,q:longint; begin q:=(p-1) div 2; b:=fastexp(alfa,2,p); if b=1 then cekprimitif:=0 else b:=fastexp(alfa,q,p); if b=1 then cekprimitif:=0 else cekprimitif:=1; end; {Fungsi Untuk Mencari Elemen Primitif acak} function primitif(p:longint):longint; var alfa:longint; begin repeat randomize; alfa:=random(p-2)+1; until cekprimitif(alfa,p)=1; primitif:=alfa; end; {Prosedur Pembangunan Kunci (Secara Acak)} procedure keygen; begin p:=primaaman; alfa:=primitif(p); a:=random(p-3)+1; beta:=fastexp(alfa,a,p); writeln(' Kunci Publik : (p,alfa,beta) = (',p,',',alfa,',',beta,')'); writeln(' Kunci Rahasia : a = ',a); end; {Prosedur Menampilkan Logo Atas} procedure logo; begin writeln; writeln('********************************************************'); writeln('* Program Pengamanan Pesan Rahasia *'); writeln('*Menggunakan Algoritma Kriptografi Kunci Publik ElGamal*'); writeln('* *'); writeln('*Copyright (C) 2007 M. Zaki Riyanto, http://zaki.web.ugm.ac.id *'); writeln('*Program Studi Matematika FMIPA Universitas Gadjah Mada*'); writeln(' *******************************************************'); writeln; end; procedure keygen_kunci_otomatis; begin repeat keygen; write(' Gunakan kunci ini (y/n) : ');readln(tombol); writeln; until tombol='y'; end; procedure masukkan_kunci_pilihan; begin repeat repeat write(' Bilangan prima aman >255 p = ');readln(p); if cekprimaaman(p)=0 then writeln(' ',p,' bukan bilangan prima aman'); if p<255 then writeln(' Masukkan p>255');writeln; until cekprimaaman(p)=1; until p>255; repeat write(' Elemen primitif alfa = ');readln(alfa); if cekprimitif(alfa,p)=0 then writeln(' ',alfa,' bukan elemen primitif'); writeln; until cekprimitif(alfa,p)=1; write(' Bilangan bulat rahasia dalam [0,',p-2,'] a = '); readln(a); if a > (p-2) then begin writeln(' ',a,' di luar interval');writeln; write(' Bilangan bulat rahasia dalam [0,',p-2,'] a = '); readln(a); end else if a < 0 then begin writeln(' ',a,' di luar interval');writeln; write(' Bilangan bulat rahasia dalam [0,',p-2,'] a = '); readln(a); end; beta:=fastexp(alfa,a,p); writeln; writeln(' Kunci Publik : (p,alfa,beta) = (',p,',',alfa,',',beta,')'); writeln(' Kunci Rahasia : a = ',a); writeln; readln; end; {prosedur Pembentukan Kunci} procedure pembentukankunci; begin clrscr; logo; writeln(' Pembentukan Kunci'); writeln; writeln(' 1. Buat kunci otomatis'); writeln(' 2. Masukkan kunci pilihan Anda'); writeln(' 3. Kembali ke menu utama'); writeln; write(' Pilihan = ');readln(pilihan); writeln; case pilihan of 1: begin keygen_kunci_otomatis; end; 2: begin masukkan_kunci_pilihan; end; 3: begin end; end; end; {Prosedur memasukkan kunci publik} procedure masukkan_kunci_publik; begin writeln(' Masukkan kunci publik (p,alfa,beta) :'); write(' p = ');readln(p); write(' alfa = ');readln(alfa); write(' beta = ');readln(beta); end; {Prosedur memasukkan kunci publik dekripsi} procedure masukkan_kunci_publik_dekripsi; begin write(' Masukkan kunci publik p = ');readln(p); end; {Memotong Pesan Menjadi Blok-Blok per karakter } procedure potong1karakter; begin for i:=1 to n do begin m[i]:=ord(pesan[i]); end; end; {Prosedur Enkripsi} procedure enkripsi; begin clrscr; logo; writeln(' Enkripsi Pesan');writeln; if (alfa+beta)=0 then masukkan_kunci_publik else begin write(' Gunakan kunci publik (',p,',',alfa,',',beta,') (y/n) = '); readln(tombol); if tombol='n' then masukkan_kunci_publik; end; {Memasukkan Plainteks} writeln; writeln(' Masukkan Pesan (maksimum 1000 karakter) :'); writeln; write(' Pesan = ');readln(pesan); n:=ord(pesan[0]); writeln; potong1karakter; writeln(' Plainteks :'); for i:=1 to n do begin writeln(' m',i,' = ',m[i]); end; writeln; writeln(' Tentukan bilangan k dalam [0,',p-2,']'); writeln(' 1. Pilih k secara acak'); writeln(' 2. Pilih k tertentu'); writeln; write(' Pilihan (1/2) = ');readln(pilihan);writeln; case pilihan of 1: begin writeln(' Cipherteks :'); for i:=1 to n do begin k:=random(p-2); gamma[i]:=fastexp(alfa,k,p); delta[i]:=(m[i]*fastexp(beta,k,p)) mod p; write(' (gamma',i,',','delta',i,') = '); write('(',gamma[i],',',delta[i],')'); writeln; end; end; 2: begin writeln(' Cipherteks :'); for i:=1 to n do begin write(' k',i,' = ');read(k); gamma[i]:=fastexp(alfa,k,p); delta[i]:=(m[i]*fastexp(beta,k,p)) mod p; write(' (gamma',i,',','delta',i,') = '); write('(',gamma[i],',',delta[i],')'); writeln; readln; end; end; end; writeln; readln; end; procedure menu_enkripsi; begin clrscr; logo; writeln(' Enkripsi'); writeln; writeln(' 1. Enkripsi pesan '); writeln(' 2. Kembali ke menu utama'); writeln; write(' Pilihan (1/2) = ');readln(pilihan); writeln; case pilihan of 1: begin enkripsi; end; 2: begin end; end; end; {Prosedur Dekripsi} procedure dekripsi; begin clrscr; logo; writeln(' Dekripsi Cipherteks Pesan');writeln; if (p+a)=0 then begin write(' Masukkan kunci publik p = ');readln(p); end else begin write(' Gunakan kunci publik p = ',p,' (y/n) = '); readln(tombol); writeln; if tombol='n' then masukkan_kunci_publik_dekripsi; end; writeln; writeln(' Masukkan cipherteks (gamma, delta), masukkan 0 untuk berhenti '); writeln; j:=0; repeat j:=j+1; write(' gamma',j,' = ');readln(gm[j]); write(' delta',j,' = ');readln(d[j]); writeln; until gm[j]=0; writeln; write(' Masukkan kunci rahasia a = ');readln(a); writeln; write(' Pesan Asli = '); for i:=1 to (j-1) do begin m[i]:=(fastexp(gm[i],p-1-a,p)*d[i]) mod p; write(chr(m[i])); end; readln; end; procedure dekripsi_hasil; begin clrscr; logo; writeln(' Dekripsi Cipherteks :'); writeln; writeln(' Cipherteks :'); writeln; for i:=1 to n do begin write(' (gamma',i,',','delta',i,') = '); writeln('(',gamma[i],',',delta[i],')'); end; writeln; write(' Masukkan kunci rahasia a = ');readln(a); writeln; write(' Pesan Asli = '); for i:=1 to n do begin m[i]:=(fastexp(gamma[i],p-1-a,p)*delta[i]) mod p; write(chr(m[i])); end; readln; end; procedure menu_dekripsi; begin clrscr; logo; writeln(' Dekripsi Cipherteks'); writeln; writeln(' 1. Dekripsi cipherteks '); writeln(' 2. Dekripsi cipherteks hasil sebelumnya'); writeln(' 3. Kembali ke menu utama'); writeln; write(' Pilihan (1-3) = ');readln(pilihan); writeln; case pilihan of 1: begin dekripsi; end; 2: begin dekripsi_hasil; end; 3: begin end; end; end; {Prosedur Representasi Bilangan Bulat (b-adic)} Procedure badic; begin writeln(' Representasi Bilangan Bulat (b-adic)');writeln; write(' Masukkan bilangan bulat nonnegatif a = ');readln(a); write(' Masukkan bilangan bulat basis >1 b = ');readln(b); writeln; write(' ',a,' = ('); ar:=a; gr:=b; bs:=b; f:=ln(ar)/ln(gr); n:=trunc(f); i:=0; x:=a; q:=x div b; ai:=x-(q*b); c:=ai; while q>0 do begin i:=i+1; x:=q; q:=x div b; ai:=x-(q*b); z[i]:=ai; end; for i:=n downto 1 do begin write(z[i],' '); end; write(c,') basis ',bs); end; {Algoritma Euclide} Procedure euclide; begin writeln(' Algoritma Euclide untuk menghitung gcd(a,b)'); writeln; repeat writeln(' Masukkan bilangan bulat a dan b dengan a > b'); write(' a = ');readln(a); write(' b = ');readln(b); writeln; if (a b); writeln; x1:=a; x2:=b; if x1<0 then x1:=-x2; if x2<0 then x2:=-x2; r:=x1 mod x2; if r=0 then x1:=x2 else begin while r <> 0 do begin r:=x1 mod x2; q:=x1 div x2; writeln(' ',x1,' = (',q,').(',x2,') + ',r); x1:=x2; x2:=r; end; end; writeln; writeln(' Nilai gcd(',a,',',b,') = ',x1); end; {Prosedur Algoritma Euclide yang diperluas} Procedure euclidediperluas; begin writeln(' Algoritma Euclide yang diperluas'); writeln; repeat writeln(' Masukkan bilangan bulat a dan b dengan a >= b'); write(' a = ');readln(a); write(' b = ');readln(b); writeln; if (a b); u:=a; v:=b; if b=0 then begin d1:=a; x:=1; y:=0; writeln(' Nilai gcd(',u,',',v,') = ',d1); writeln(' Nilai x = ',x); writeln(' Nilai y = ',y); end else begin x2:=1; x1:=0; y2:=0; y1:=1; while b>0 do begin q:=a div b; r:=a-(q*b); x:=x2-(q*x1); y:=y2-(q*y1); a:=b; b:=r; x2:=x1; x1:=x; y2:=y1; y1:=y; end; d1:=a; x:=x2; y:=y2; writeln(' Nilai gcd(',u,',',v,') = ',d1); writeln(' Nilai x = ',x); writeln(' Nilai y = ',y); end; end; {Prosedur Mencari Invers Pergandaan} procedure invers; begin writeln(' Mencari Invers Pergandaan a mod m'); writeln; write(' Masukkan bilangan bulat a = ');readln(a); write(' Masukkan bilangan bulat positif m = ');readln(mp); writeln; u:=a; v:=mp; a:=a mod v; if mp=0 then begin d1:=a; x:=1; y:=0; x:=x+v; x:=x mod v; if d1>1 then writeln(' ',u,' tidak punya invers mod ',v) else writeln(' Invers ',u,' modulo ',v,' adalah ',x); end else begin x2:=1; x1:=0; y2:=0; y1:=1; while mp>0 do begin q:=a div mp; r:=a-(q*mp); x:=x2-(q*x1); y:=y2-(q*y1); a:=mp; mp:=r; x2:=x1; x1:=x; y2:=y1; y1:=y; end; d1:=a; x:=x2; y:=y2; x:=x+v; x:=x mod v; if d1>1 then writeln(' ',u,' tidak punya invers mod ',v) else writeln(' Invers ',u,' modulo ',v,' adalah ',x); end; end; {Prosedur Tes Fermat} Procedure tesfermat; begin writeln(' Tes Keprimaan Fermat'); writeln; write(' Masukkan bilangan bulat positif ganjil >2 p = '); readln(p); write(' Masukkan bilangan parameter positif t = ');readln(t); for i:=1 to t do begin writeln; write(' Ambil bilangan bulat a di dalam [2, ',p-1,'] a ='); readln(a); y:=fastexp(a,p-1,p); writeln; if y <> 1 then writeln(' ',p,' adalah bilangan komposit') else writeln(' ',p,' adalah bilangan prima'); end; end; {Prosedur Menu Tes Miller-Rabbin} procedure menutesmillerrabbin; begin writeln(' Tes Keprimaan Miller-Rabbin'); repeat writeln; write(' Masukkan bilangan bulat positif ganjil >2 p ='); readln(p); if (p mod 2)=0 then writeln(' ',p,' genap'); until (p mod 2)=1; write(' Masukkan bilangan parameter positif t = ');readln(t); x:=p; k:=0; writeln; repeat x:=x div 2; k:=k+1; until x mod 2) <> 0; writeln(' ',p-1,' = ',x,' x 2^',k); writeln; if mrtest(p,t)=1 then writeln(' ',p,' adalah bilangan prima'); if mrtest(p,t)=0 then writeln(' ',p,' adalah bilangan komposit'); end; {Prosedur Menu Metode Fast Exponentiation} procedure menufastexp; begin writeln(' Menghitung a^k mod p menggunakan metode fast exponentiation'); writeln; write(' Masukkan bilangan bulat positif a = ');readln(a); write(' Masukkan bilangan bulat positif k = ');readln(k); write(' Masukkan bilangan bulat positif p = ');readln(p); writeln; write(' ',a,'^',k,' mod ',p,' = ',fastexp(a,k,p)); writeln; end; {Prosedur Menu Tes Prima Biasa} procedure menutesprima; begin writeln(' Tes Bilangan Prima Biasa'); writeln; write(' Masukkan bilangan bulat >1 p = ');readln(p); writeln; if cekprima(p)=1 then writeln(' ',p,' adalah bilangan prima'); if cekprima(p)=0 then writeln(' ',p,' adalah bilangan komposit'); writeln; end; {Prosedur Menu Tes Prima Aman} procedure menutesprimaaman; begin writeln(' Tes Bilangan Prima Aman'); writeln; writeln(' Masukkan bilangan bulat p > 1 '); writeln; write(' p = ');readln(p); writeln; if cekprima(p)=0 then writeln(' ',p,' adalah bilangan komposit'); if cekprima(p)=1 then begin if cekprimaaman(p)=1 then writeln(' ',p,' adalah bilangan prima aman'); if cekprimaaman(p)=0 then writeln(' ',p,' adalah bilangan prima, tetapi bukan bilangan prima aman'); end; writeln; end; {Prosedur Menu Tes Elemen Primitif} procedure menutesprimitif; begin writeln(' Tes elemen primitif Zp*, untuk p prima aman'); writeln; repeat repeat write(' Masukkan bilangan prima aman p = '); readln(p); writeln; if cekprima(p)=0 then begin writeln(' ',p,' bukan bilangan prima'); writeln; end; until cekprima(p)=1; if cekprimaaman(p)=0 then begin writeln; writeln(' ',p,' bukan bilangan prima aman'); end; until cekprimaaman(p)=1; writeln(' Masukkan sebarang a elemen Z',p,'* : (a=0 untuk berhenti)'); repeat write(' a = ');readln(a); writeln; if cekprimitif(a,p)=1 then writeln(' ',a,' adalah elemen primitif'); if cekprimitif(a,p)=0 then writeln(' ',a,' bukan elemen primitif'); writeln; until a=0; end; {Prosedur Menu Lihat Semua Elemen Primitif} procedure lihatsemuaprimitif; begin writeln(' Tampilkan semua elemen primitif Zp*, untuk p prima aman :'); writeln; repeat repeat write(' Masukkan bilangan prima aman p = '); readln(p); writeln; if cekprima(p)=0 then begin writeln(' ',p,' bukan bilangan prima'); writeln; end; until cekprima(p)=1; if cekprimaaman(p)=0 then begin writeln; writeln(' ',p,' bukan bilangan prima aman'); end; until cekprimaaman(p)=1; writeln; writeln(' Elemen-elemen primitif Z',p,'* adalah :'); writeln; w:=0; for x:=2 to (p-1) do begin if cekprimitif(x,p)=1 then begin w:=w+1; write(' ',x,' '); end; end; writeln; writeln; writeln(' Banyaknya bilangan = ',w); end; {Prosedur Menu Lihat Semua Bilangan Prima} procedure menulihatprima; begin writeln(' Tampilkan semua bilangan prima di antara a dan b'); writeln; write(' Masukkan bilangan >1, a = ');readln(a); write(' Masukkan bilangan >',a,', b = ');readln(b); writeln; w:=0; writeln(' Bilangan-bilangan prima di antara ',a,' dan ',b,' adalah :'); for i:=a to b do begin if cekprima(i)=1 then begin w:=w+1; write(' ',i); end; end; writeln; writeln; writeln(' Banyaknya bilangan = ',w); end; {Prosedur Menu Lihat Semua Bilangan Prima Aman} procedure menulihatprimaaman; begin writeln(' Tampilkan semua bilangan prima aman di antara a dan b'); writeln; repeat write(' Masukkan bilangan >4, a = ');readln(a); if a<5 then writeln(' Pemilihan bilangan salah'); writeln; until a>4; repeat write(' Masukkan bilangan >',a,' b = ');readln(b); if ba; writeln; writeln(' Bilangan-bilangan prima aman di antara ',a,' dan ',b,' adalah :'); w:=0; for i:=a to b do begin if cekprimaaman(i)=1 then begin w:=w+1; write(' ',i); end; end; writeln; writeln; writeln(' Banyaknya bilangan = ',w); end; {cek relatif prima a dan b} procedure menu_cek_relatif_prima; begin writeln(' Cek apakah a dan b relatif prima'); writeln; write(' Masukkan bilangan a = ');readln(a); write(' Masukkan bilangan b = ');readln(b); writeln; if gcd(a,b)=1 then writeln(' ',a,' dan ',b,' relatif prima') else writeln(' ',a,' dan ',b,' tidak relatif prima'); writeln; end; {Lihat Elemen Zn Yang Relatif Prima dengan n} procedure menu_lihat_elemen_relatif_prima; begin writeln(' Lihat elemen-elemen Zn yang relatif prima dengan n'); writeln; write(' Masukkan bilangan >2 n = ');readln(n); writeln; writeln(' Elemen-elemen Z',n,' yang relatif prima dengan ',n,' adalah :'); w:=0; for i:=1 to (n-1) do begin if gcd(i,n)=1 then begin write(' ',i); w:=w+1; end; end; writeln; writeln; writeln(' Banyaknya bilangan = ',w); end; {Prosedur Program Tambahan} procedure programtambahan; begin clrscr; logo; writeln(' Program Tambahan'); writeln; writeln(' 1. Representasi bilangan bulat (b-adic)'); writeln(' 2. Algoritma Euclide untuk menghitung gcd(a,b)'); writeln(' 3. Algoritma Euclide yang diperluas'); writeln(' 4. Hitung a^k mod p (metode fast exponentiation)'); writeln(' 5. Mencari invers pergandaan a mod m'); writeln(' 6. Tes keprimaan Fermat'); writeln(' 7. Tes keprimaan Miller-Rabbin'); writeln(' 8. Tes keprimaan biasa'); writeln(' 9. Tes bilangan prima aman'); writeln(' 10. Tampilkan semua bilangan prima di antara a dan b'); writeln(' 11. Tampilkan semua bilangan prima aman di antara a dan b'); writeln(' 12. Tes elemen primitif Zp*, untuk p prima aman'); writeln(' 13. Tampilkan semua elemen primitif Zp*, untuk p prima aman'); writeln(' 14. Cek apakah a dan b relatif prima'); writeln(' 15. Lihat elemen-elemen Zn yang relatif prima dengan n'); writeln(' 16. Kembali ke menu utama'); writeln; write(' Pilihan (1-16) = ');readln(pilihan); writeln; case pilihan of 1: begin clrscr; logo; badic; readln; end; 2: begin clrscr; logo; euclide; readln; end; 3: begin clrscr; logo; euclidediperluas; readln; end; 4: begin clrscr; logo; menufastexp; readln; end; 5: begin clrscr; logo; invers; readln; end; 6: begin clrscr; logo; tesfermat; readln; end; 7: begin clrscr; logo; menutesmillerrabbin; readkey; end; 8: begin clrscr; logo; menutesprima; readkey; end; 9: begin clrscr; logo; menutesprimaaman; readkey; end; 10: begin clrscr; logo; menulihatprima; readkey; end; 11: begin clrscr; logo; menulihatprimaaman; readkey; end; 12: begin clrscr; logo; menutesprimitif; end; 13: begin clrscr; logo; lihatsemuaprimitif; readkey; end; 14: begin clrscr; logo; menu_cek_relatif_prima; readkey; end; 15: begin clrscr; logo; menu_lihat_elemen_relatif_prima; readkey; end; 16: begin clrscr; end; end; end; {Prosedur Menampilkan Menu Depan} procedure menuutama; begin clrscr; logo; writeln(' Menu Utama'); writeln; writeln(' 1. Pembentukan kunci'); writeln(' 2. Enkripsi'); writeln(' 3. Dekripsi'); writeln(' 4. Program tambahan'); writeln(' 5. Keluar'); writeln; write(' Pilihan (1-5) = ');readln(pilihan); writeln; case pilihan of 1: begin pembentukankunci; menuutama; end; 2: begin menu_enkripsi; menuutama; end; 3: begin menu_dekripsi; menuutama; end; 4: begin programtambahan; menuutama; end; 5: begin clrscr; end; end; end; {Program Utama} begin p:=0; alfa:=0; beta:=0; a:=0; menuutama; end. { ### ======================= end of file ======================= ### }