LAMPIRAN
14
1. Algoritme Aritmetika a. Prosedur UbahBinKeDes Deskripsi : Prosedur mengubah Vektor Biner ke Desimal dari Order Rendah ke Order Tinggi UbahBinKeDes := proc( N::list ) local D1, D2 :: list, Des::integer; D1:=map(x -> 2^x,[seq(i,i=0..(nops(N)-1))]): D2:=[seq(N[j]*D1[j],j=1..nops(N))]: Des:=add( i, i=D2 ); end proc: b. Prosedur UbahDesKeBin Deskripsi : Prosedur mengubah Desimal ke Vektor Biner dari Order Rendah ke Order Tinggi UbahDesKeBin := proc(B::integer,m::integer) local K,KVek,Kv::list, i::integer: K := B mod 2^m; Kv:=convert(K,base,2): KVek:=[op(Kv),seq(0*i,i=(nops(Kv)+1)..m)]: end proc: c. Prosedur UbahBinKeSet Deskripsi : Prosedur mengubah Vektor Biner ke dalam himpunan (dari Order Rendah ke Order Tinggi) UbahBinKeSet:= proc( Cr::list) local H::set, i,n::integer: n := nops(Cr): H:={}: for i from 1 to n do if Cr[i]=1 then H:=H union {i-1}: end if: end do: return(H): end proc: d. Prosedur UbahDesKeSet Deskripsi : Prosedur mengubah bilangan desimal ke dalam bentuk himpunan UbahDesKeSet:=proc(n::integer) local X::list: X:=convert(n,base,2): UbahBinKeSet(X); end proc: e. Prosedur UbahSetKeDes Deskripsi : Prosedur mengubah bentuk himpunan ke dalam bilangan desimal UbahSetKeDes := proc( N::set ) local D::set, Des::integer; D:=map(x -> 2^x,N): Des:=add( i, i=D ); end proc: f. Prosedur UbahSetKeBin Deskripsi : Prosedur mengubah bentuk himpunan ke dalam Vektor Biner UbahSetKeBin := proc( N::set, m::integer ) local D::set, Des::integer; Des:=UbahSetKeDes(N): UbahDesKeBin(Des,m); end proc: g. Prosedur AcakSet Deskripsi : Prosedur untuk membangkitkan himpunan acak dalam AcakSet:=proc(m::posint) local AcIn::procedure, p::integer:
15
h.
i.
j.
k.
l.
m.
AcIn := rand(2^m): p:=AcIn(): UbahDesKeSet(p); end proc: Prosedur AdisiSet Deskripsi : Prosedur menjumlahkan dua himpunan AdisiSet:=proc(S::set,T::set) return((S union T) minus (S intersect T)); end proc: Prosedur ReduSet Deskripsi : Prosedur menghilangkan nilai 0 pada vektor biner ReduSet:=proc(n::integer,m::posint) local H,G,K,S::set, i,j,k::integer: S:=DatB[m]: if n<0 or n>(2*m-2) then return(false): elif 0<=n and n<m then return({n}); else H:=map(x->(x+(n-m)),S); end if: return(H): end proc: Prosedur ModSet Deskripsi : Prosedur untuk menentukan dimana merupakan set ModSet:=proc(T::set,m::posint) local G,K,H,R::set, i::integer: if max(op(T))>(2*m-2) then error end if; R:={seq(i,i=m..(2*m-2))}: K:= T intersect R: G:=T: for i while K<>{} do H:=ReduSet(max(op(K)),m): G:=AdisiSet(G minus {max(op(K))},H): K:= G intersect R: end do: return(G); end proc: Prosedur KaliSet Deskripsi : Prosedur untuk mengalikan set KaliSet:=proc(A::set,B::set) local H::set, i,j::integer: H:={}: for i in A do H:=AdisiSet(H,map(j->(j+i),B)): end do: return(H): end proc: Prosedur MultiSet Deskripsi : Prosedur mengalikan set dengan menggunakan modulo MultiSet:=proc(A::set,B::set,m::integer) local H::set: H:=KaliSet(A,B): ModSet(H,m); end proc: Prosedur BagiSet Deskripsi : Prosedur membagi set BagiSet:=proc(T::set,S::set) local K,Q,R::set, i,r,s,t::integer: R:=T: Q:={}: r:=max(op(R)): s:=max(op(S)):
16
n.
o.
for i while r>=s do t:=r-s: Q:=Q union {t}: K:=KaliSet({t},S): R:=AdisiSet(K,R): r:=max(op(R)): end do: return([Q,R]); end proc: Prosedur InvSet Deskripsi : Prosedur mencari invers dari set InvSet:=proc(T::set,m::integer) local QA,QB,RA,RB,R,S,Tmp::set, L::list, i::integer: S:=DatB[m]: if T={} then return("Tidak ada invers") end if: RA:=S union {m}: RB:=T: QA:={}: QB:={0}: L:=BagiSet(RA,RB): RA:=RB: RB:=op(2,L): for i while RB<>{} do Tmp:=QA: QA:=QB: R:=KaliSet(QB,op(1,L)): QB:=AdisiSet(Tmp,R): L:=BagiSet(RA,RB): RA:=RB: RB:=op(2,L): end do: return(QB); end proc: Prosedur DivSet Deskripsi : Prosedur membagi A oleh B modulo m DivSet:=proc(A::set,B::set,m::integer) local iB::set: iB:=InvSet(B,m); MultiSet(A,iB,m); end proc: (Rosdiana 2009)
17
2. Konstruksi Aritmetika Kurva Eliptik a. Prosedur Menentukan Kurva Eliptik 2^m dengan 1. Supersingular m:=10; ECAcakABCSs:=proc(m::posint) local A,B,C::set,i::integer; A:=AcakSet(m); B:=AcakSet(m); C:=AcakSet(m); for i while B={}do B:=AcakSet(m); end do; for i while C={}do C:=AcakSet(m); end do; return ([A,B,C]); end proc: Contoh : K:=ECAcakABCSs(m); 2.
Non-Supersingular ECAcakABNs:=proc(m::posint) local A,B::set,i::integer; A:=AcakSet(m); B:=AcakSet(m); for i while B={}do B:=AcakSet(m); end do; return ([A,B]); end proc: Contoh : K:=ECAcakABNs(m);
b. Prosedur Menentukan Titik-titik Kurva Eliptik 2^m 1. Supersingular AcakPtSs:=proc(K::list,m::posint) local X,Y,H,G,T,U,S::set, i,t::integer: X:=AcakSet(m); Y:=AcakSet(m); H:=MultiSet(K[3],Y,m); G:=MultiSet(Y,Y,m); H:=AdisiSet(G,H); G:=MultiSet(X,X,m); T:=MultiSet(X,G,m); H:=AdisiSet(H,T); U:=MultiSet(K[1],X,m); H:=AdisiSet(H,U); S:=AdisiSet(H,K[2]); for i while S<>{} do X:=AcakSet(m); Y:=AcakSet(m); H:=MultiSet(K[3],Y,m); G:=MultiSet(Y,Y,m); H:=AdisiSet(G,H);
18
G:=MultiSet(X,X,m); T:=MultiSet(X,G,m); H:=AdisiSet(H,T); U:=MultiSet(K[1],X,m); H:=AdisiSet(H,U); S:=AdisiSet(H,K[2]); end do: return([X,Y]); end proc: Contoh : P:=AcakPtSs(K,m); 2.
Non-Supersingular AcakPtNS:=proc(K::list,m::posint) local X,Y,H,G,T,U,S::set, i,t::integer: X:=AcakSet(m); Y:=AcakSet(m); H:=MultiSet(X,Y,m); G:=MultiSet(Y,Y,m); H:=AdisiSet(G,H); G:=MultiSet(X,X,m); T:=MultiSet(X,G,m); H:=AdisiSet(H,T); U:=MultiSet(K[1],G,m); H:=AdisiSet(H,U); S:=AdisiSet(H,K[2]); for i while S<>{} do X:=AcakSet(m); Y:=AcakSet(m); H:=MultiSet(X,Y,m); G:=MultiSet(Y,Y,m); H:=AdisiSet(G,H); G:=MultiSet(X,X,m); T:=MultiSet(X,G,m); H:=AdisiSet(H,T); U:=MultiSet(K[1],G,m); H:=AdisiSet(H,U); S:=AdisiSet(H,K[2]); end do: return([X,Y]); end proc: Contoh : P:=AcakPtNs(K,m);
c. Prosedur Aritmetika Kurva Eliptik 2^m 1. Supersingular AddPtBinSs:=proc(X::list,Y::list,K::list,m::posint) local A,B,T,S,L,H,G::set: if X=[{},{}] or Y=[{},{}] then A:=AdisiSet(X[1],Y[1]); B:=AdisiSet(X[2],Y[2]); return([A,B]); end if: T:=AdisiSet(X[2],Y[2]); if X[1]=Y[1] and T=K[3] then return([{},{}]); elif X<>Y then T:=AdisiSet(X[1],Y[1]):
19
S:=AdisiSet(X[2],Y[2]): L:=DivSet(S,T,m): H:=MultiSet(L,L,m): H:=AdisiSet(H,T): G:=AdisiSet(H,X[1]): G:=MultiSet(G,L,m); G:=AdisiSet(G,X[2]): G:=AdisiSet(G,K[3]): return([H,G]); else T:=MultiSet(X[1],X[1],m): L:=AdisiSet(K[1],T): L:=DivSet(L,K[3],m): H:=MultiSet(L,L,m): G:=AdisiSet(H,X[1]): G:=MultiSet(G,L,m); G:=AdisiSet(G,X[2]): G:=AdisiSet(G,K[3]): return([H,G]); end if: end proc: Contoh : Infinity:=AddPtBinSs(P,nP,K,m); Q:=AcakPtSs(K,m); F:=AcakPtSs(K,m); Periksa Komutatif R:=AddPtBinSs(Q,F,K,m); S:=AddPtBinSs(F,Q,K,m);
Periksa Assosiatif M:=AcakPtSs(K,m): V:=AddPtBinSs(F,M,K,m): C:=AddPtBinSs(M,Q,K,m): V:=AddPtBinSs(V,Q,K,m); V:=AddPtBinSs(F,C,K,m); 2.
Non-Supersingular AddPtBinNs:=proc(X::list,Y::list,K::list,m::posint) local A,B,T,S,L,U::set: if X=[{},{}] or Y=[{},{}] then A:=AdisiSet(X[1],Y[1]); B:=AdisiSet(X[2],Y[2]); return([A,B]); end if: T:=AdisiSet(X[2],Y[2]); if X[1]=Y[1] and T=X[1] then A:={}: B:={}: return([A,B]); elif X<>Y then U:=AdisiSet(X[1],Y[1]): S:=AdisiSet(X[2],Y[2]): L:=DivSet(S,U,m):
20
T:=MultiSet(L,L,m): A:=AdisiSet(L,T): A:=AdisiSet(A,K[1]): A:=AdisiSet(A,U): B:=AdisiSet(X[2],A): S:=AdisiSet(X[1],A): S:=MultiSet(S,L,m): B:=AdisiSet(B,S): return([A,B]); else S:=MultiSet(X[1],X[1],m): T:=DivSet(K[2],S,m): A:=AdisiSet(S,T): T:=DivSet(X[2],X[1],m): L:=AdisiSet(X[1],T): B:=MultiSet(A,L,m): B:=AdisiSet(B,S): B:=AdisiSet(A,B): return([A,B]); end if: end proc: Contoh : Q:=AcakPtNs(K,m); F:=AcakPtNs(K,m); Periksa Komutatif R:=AddPtBinNs(Q,F,K,m); R:=AddPtBinNs(F,Q,K,m); Periksa Assosiatif M:=AcakPtNs(K,m): V:=AddPtBinNs(F,M,K,m): C:=AddPtBinNs(M,Q,K,m): V:=AddPtBinNs(V,Q,K,m); V:=AddPtBinNs(F,C,K,m); d. Prosedur Negasi Titik 1. Supersingular NegPtSs:=proc(P::list,K::list,m::posint) local H::set, i::integer: H:=AdisiSet(P[2],K[3]): subsop(2=H,P); end proc: Contoh : nP:=NegPtSs(P,K,m); P; Infinity:=AddPtBinSs(P,nP,K,m); 2.
Non-Supersingular NegPtNs:=proc(P::list,K::list,m::posint) local H::set, i::integer: H:=AdisiSet(P[1],P[2]); subsop(2=H,P);
21
end proc: Contoh : nP:=NegPtNs(P,K,m); P; Infinity:=AddPtBinNs(P,nP,K,m); e. Prosedur Kelipatan titik P sebanya k kali 1. Supersingular MulPtBinSs:=proc(P::list,k::integer,K::list,m::posint) local H,G,X::list, i::integer: X:=convert(k,base,2); G:=P: H:=[{},{}]: if op(1,X)=1 then H:=G: end if: for i from 2 to nops(X) do G:=AddPtBinSs(G,G,K,m); if op(i,X)=1 then H:=AddPtBinSs(H,G,K,m): end if: end do: return(H); end proc: Contoh: R:=MulPtBinSs(P,5,K,m): T:=MulPtBinSs(R,6,K,m); S:=MulPtBinSs(P,6,K,m): S:=MulPtBinSs(S,5,K,m); 2.
Non-Supersingular MulPtBinNs:=proc(P::list,k::integer,K::list,m::posint) local H,G,X::list, i::integer: X:=convert(k,base,2); G:=P: H:=[{},{}]: if op(1,X)=1 then H:=G: end if: for i from 2 to nops(X) do G:=AddPtBinNs(G,G,K,m); if op(i,X)=1 then H:=AddPtBinNs(H,G,K,m): end if: end do: return(H); end proc: Contoh: R:=MulPtBinNs(P,5,K,m): T:=MulPtBinNs(R,6,K,m); S:=MulPtBinNs(P,6,K,m): S:=MulPtBinNs(S,5,K,m);
22
3. ElGamal a. Prosedur Yang Digunakan Secara Rutin (mencari , , dan a) p := nextprime(rand(1..10^40)()); p := 9574006709478958762709029785327385064807;
alpha := 5; a := rand(10..p-10)() mod p; a := 665638090635425982769337333168305062441; beta := Power(alpha,a) mod p;
b. Kunci Publik dan Kunci Privat KunciPublik := [p,alpha,beta];
KunciPribadi := a; c. Enkripsi Pesan := 91819250104; k := rand(10..p-10)(); k := 1026468764312794860407049035579406321411; gama := Power(alpha,k) mod p; Topeng := (Power(beta,k) mod p); delta := Topeng*(Pesan) mod p;
Kirim := [gama,delta];
d. Dekripsi Topeng := Power(Kirim[1],a) mod p; BukaTopeng := 1/Topeng mod p; PesanDiTerima := Kirim[2]*BukaTopeng mod p; PesanDiTerima := Kirim[2]*(Power(1/Kirim[1],a) mod p) mod p;
(Menezes et al. 1996)
23
4. ElGamal Kurva Eliptik a. Prosedur Yang Digunakan Secara Rutin Prosedur yang digunakan sama dengan kurva eliptik, hanya saja ditambah prosedur kasus supersingular dan non-supersingular untuk mencari kurva, titik, proses adisi, dan kelipatan titik untuk masing-masing kasus. b. Pembuatan Kunci with(RandomTools): 1. Supersingular Privat:=Generate(integer(range=1..99)); m:=10; K:=ECAcakABCSs(m);
alpha:=AcakPtSs(K,m); beta:=MulPtBinSs(alpha,Privat,K,m); Publik:=[alpha,beta];
2.
Non-Supersingular Privat:=Generate(integer(range=1..99)); m:=10; K:=ECAcakABNs(m);
alpha:=AcakPtNs(K,m); beta:=MulPtBinNs(alpha,Privat,K,m); Publik:=[alpha,beta]; c. Enkripsi 1. Supersingular Pesan:=AcakPtSs(K,m); k:=Generate(integer(range=1..99)); Publik; gama:=MulPtBinSs(Publik[1],k,K,m); N:=MulPtBinSs(Publik[2],k,K,m); delta:=AddPtBinSs(Pesan,N,K,m); kirim:=[gama,delta];
2.
Non-Supersingular Pesan:=AcakPtNs(K,m); k:=Generate(integer(range=1..99));
24
Publik; gama:=MulPtBinNs(Publik[1],k,K,m); N:=MulPtBinNs(Publik[2],k,K,m); delta:=AddPtBinNs(Pesan,N,K,m); kirim:=[gama,delta];
d. Dekripsi 1. Supersingular kirim; w:=MulPtBinSs(kirim[1],Privat,K,m); w:=NegPtSs(w,K,m); Terima:=AddPtBinSs(kirim[2],w,K,m);
convert(Pesan=Terima,'truefalse'); # digunakan untuk memastikan apakah Pesan sebelum dienkripsi sama dengan Pesan setelah didekripsikan. 2.
Non-Supersingular kirim; w:=MulPtBinNs(kirim[1],Privat,K,m); w:=NegPtNs(w,K,m); Terima:=AddPtBinNs(kirim[2],w,K,m);
convert(Pesan=Terima,'truefalse'); # digunakan untuk memastikan apakah Pesan sebelum dienkripsi sama dengan Pesan setelah didekripsikan.
