: Keamanan Sistem Komputer. Digital Signature Algorithm. : Yoga Prihastomo N I M : : Teknik Informatika

Keamanan Sistem Komputer Digital Signature Algorithm

Nama

: Yoga Prihastomo

NIM

: 2003-31-038

Mata Kuliah

: Keamanan Sistem Komputer

Jurusan

: Teknik Informatika

Keamanan Sistem Komputer

Digital Signature Algorithm

Pendahuluan Kriptografi Kriptografi, secara umum adalah ilmu dan seni untuk menjaga kerahasiaan berita [bruce Schneier - Applied Cryptography]. Kata cryptography berasal dari kata Yunani kryptos (tersembunyi) dan graphein (menulis). Selain pengertian tersebut terdapat pula pengertian ilmu yang mempelajari teknik-teknik matematika yang berhubungan dengan aspek keamanan informasi seperti kerahasiaan data, keabsahan data, integritas data, serta autentikasi data [A. Menezes, P. van Oorschot and S. Vanstone - Handbook of Applied Cryptography]. Cryptanalysis adalah aksi untuk memecahkan mekanisme kriptografi dengan cara mendapatkan plaintext atau kunci dari ciphertext yang digunakan untuk mendapatkan informasi berharga kemudian mengubah atau memalsukan pesan dengan tujuan untuk menipu penerima yang sesungguhnya, memecahkan ciphertext. Cryptology adalah ilmu yang mencakup cryptography dan cryptanalysis. Tidak semua aspek keamanan informasi ditangani oleh kriptografi. Ada empat tujuan mendasar dari ilmu kriptografi ini yang juga merupakan aspek keamanan informasi yaitu : Kerahasiaan, adalah layanan yang digunakan untuk menjaga isi dari informasi dari siapapun kecuali yang memiliki otoritas atau kunci rahasia untuk membuka/mengupas informasi yang telah disandi. Integritas data, adalah berhubungan dengan penjagaan dari perubahan data secara tidak sah. Untuk menjaga integritas data, sistem harus memiliki kemampuan untuk mendeteksi manipulasi data oleh pihak-pihak yang tidak berhak, antara lain penyisipan, penghapusan, dan pensubsitusian data lain kedalam data yang sebenarnya. Autentikasi, adalah berhubungan dengan identifikasi/pengenalan, baik secara kesatuan sistem maupun informasi itu sendiri. Dua pihak yang saling berkomunikasi harus saling memperkenalkan diri. Informasi yang dikirimkan melalui kanal harus diautentikasi keaslian, isi datanya, waktu pengiriman, dan lain-lain. Non-repudiasi., atau nirpenyangkalan adalah usaha untuk mencegah terjadinya penyangkalan terhadap pengiriman/terciptanya suatu informasi oleh yang mengirimkan/membuat. Enkripsi adalah transformasi data kedalam bentuk yang tidak dapat terbaca tanpa sebuah kunci tertentu. Tujuannya adalah untuk meyakinkan privasi dengan menyembunyikan informasi dari orang-orang yang tidak ditujukan, bahkan mereka mereka yang memiliki akses ke data terenkripsi. Dekripsi merupakan kebalikan dari enkripsi, yaitu transformasi data terenkripsi kembali ke bentuknya semula. Kriptografi saat ini lebih dari enkripsi dan dekripsi saja. Otentikasi menjadi bagian dari kehidupan kita sama seperti privasi. Kita menggunakan otentikasi dalam kehidupan sehari-hari, sebagai contoh saat kita menandatangani sejumlah dokumen dan saat kita berpindah ke dunia dimana keputusan dan persetujuan kita dikomunikasikan secara elektronis, kita membutuhkan tekikteknik untuk otentikasi. Kriptografi menyediakan mekanisme untuk prosedur semacam itu. Digital signature (tanda tangan digital) mengikat dokumen dengan kepemilikan kunci tertentu, sedangkan digital timestamp mengikat dokumen dengan pembuatnya pada saat tertentu.

Halaman

1



Standar Kriptografi Standar kriptografi dibutuhkan untuk menciptakan interoperabilitas dalam dunia keamanan informasi. Pada dasarnya standar merupakan kondisi dan protokol yang dibuat untuk memungkinkan keseragaman dalam komunikasi, transaksi dan semua aktivitas secara virtual. Evolusi teknologi informasi yang terus berlanjut memotivasi pengembangan lebih banyak lagi standar, yang membantu memandu evolusi ini. Motivasi utama dibalik standar adalah untuk memungkinkan teknologi dari pabrik yang berbeda untuk “berbicara bahasa yang sama”, untuk berinteraksi secara efektif. Dalam kriptografi, standarisasi memiliki tujuan tambahan, yaitu sebagai landasan dari teknik-teknik kriptografi karena protokol yang rumit cenderung memiliki cacat dalam rancangan. Dengan menerapkan standar yang telah diuji dengan baik, industri dapat memproduksi produk yang lebih terpercaya. Bahkan protokol yang amanpun dapat lebih dipercaya pelanggan setelah menjadi standar, karena telah melalui proses pengesahan. Pemerintah, industri privat, dan organisasi lain berkontribusi dalam pengumpulan luas standar-standar kriptografi. Beberapa dari standar-standar ini adalah ISO, ANSI, IEEE, NIST, dan IETF. Ada banyak tipe standar, beberapa digunakan dalam industri perbankan, beberapa digunakan secara internasional, dan yang lain dalam pemerintahan. Standarisasi membantu pengembang merancang standar baru, mereka dapat mengikuti standar yang telah ada dalam proses pengembangan. Dengan proses ini pelanggan memiliki kesempatan untuk memilih diantara produk atau layanan yang berkompetisi.

Algoritma Sandi Algoritma sandi adalah algoritma yang berfungsi untuk melakukan tujuan kriptografis. Algoritma tersebut harus memiliki kekuatan untuk melakukan (dikemukakan oleh Shannon): konfusi/pembingungan (confusion), dari teks terang sehingga sulit untuk direkonstruksikan secara langsung tanpa menggunakan algoritma dekripsinya difusi/peleburan (difusion), dari teks terang sehingga karakteristik dari teks terang tersebut hilang. sehingga dapat digunakan untuk mengamankan informasi. Pada implementasinya sebuah algoritmas sandi harus memperhatikan kualitas layanan/Quality of Service atau QoS dari keseluruhan sistem dimana dia diimplementasikan. Algoritma sandi yang handal adalah algoritma sandi yang kekuatannya terletak pada kunci, bukan pada kerahasiaan algoritma itu sendiri. Teknik dan metode untuk menguji kehandalan algoritma sandi adalah kriptanalisa. Dasar matematis yang mendasari proses enkripsi dan dekripsi adalah relasi antara dua himpunan yaitu yang berisi elemen teks terang /plaintext dan yang berisi elemen teks sandi/ciphertext. Enkripsi dan dekripsi merupakan fungsi transformasi antara himpunanhimpunan tersebut. Apabila elemen-elemen teks terang dinotasikan dengan P, elemen-elemen teks sandi dinotasikan dengan C, sedang untuk proses enkripsi dinotasikan dengan E, dekripsi dengan notasi D.

Halaman

2



Enkripsi : E(P) = C Dekripsi : D(C) = P atau D(E(P)) = P Secara umum berdasarkan kesamaan kuncinya, algoritma sandi dibedakan menjadi : kunci-simetris/symetric-key, sering disebut juga algoritma sandi konvensional karena umumnya diterapkan pada algoritma sandi klasik kunci-asimetris/asymetric-key Berdasarkan arah implementasi dan pembabakan jamannya dibedakan menjadi : algoritma sandi klasik classic cryptography algoritma sandi modern modern cryptography Berdasarkan kerahasiaan kuncinya dibedakan menjadi : algoritma sandi kunci rahasia secret-key algoritma sandi kunci publik publik-key Pada skema kunci-simetris, digunakan sebuah kunci rahasia yang sama untuk melakukan proses enkripsi dan dekripsinya. Sedangkan pada sistem kunci-asimentris digunakan sepasang kunci yang berbeda, umumnya disebut kunci publik(public key) dan kunci pribadi (private key), digunakan untuk proses enkripsi dan proses dekripsinya. Bila elemen teks terang dienkripsi dengan menggunakan kunci pribadi maka elemen teks sandi yang dihasilkannya hanya bisa didekripsikan dengan menggunakan pasangan kunci pribadinya. Begitu juga sebaliknya, jika kunci pribadi digunakan untuk proses enkripsi maka proses dekripsi harus menggunakan kunci publik pasangannya

Digital Signature Algorithm (DSA) Tanda tangan digital DSA berbentuk sepasang besar angka yang ditampilkan komputer sebagai string dari digit biner. Tanda tangan digital dihitung dengan menggunakan sejumlah aturan dan sejumlah parameter sehingga identitas pemilik dan integritas data dapat diverifikasi. Pembuat tanda tangan menggunakan kunci privat untuk membuat tanda tangan; sedangkan kunci publik, yang berkorespodensi dengan kunci privat namun tidak sama, digunakan untuk memverifikasi tanda tangan. Setiap user memiliki sepasang kunci publik dan kunci privat. kunci publik diasumsikan diketahui public secara umum, sedangkan kunci privat tidak pernah disebar. DSA dapat dilihat sebagai variasi dari skema tanda tangan ElGamal. Keamanan DSA berdasarkan pada kemampuan logaritma diskrit dalam urutan bilangan prima Z*p. Domain parameter DSA dibangkitkan untuk setiap entitas dalam domain keamanan tertentu : 1. Pilih bilangan prima sepanjang 160 bit dan 1024 bit dengan kondisi : q | p – 1 2. Pilih pembangkit g yang memiliki kelompok putaran yang unik di mana q berada dalam Z*p. Pilih sebuah elemen h ε Z*p dan hitung g = h (p-1)/q mod p. Ulangi hingga g ≠ 1 3. Parameter domain adalah p, q dan g.

Halaman

3



Setiap entitas A dalam domain, dengan domain parameter (p,q,g) melakukan : 1. pilih bilangan acak x dengan ketentuan 1 ≤ x ≤ q−1 2. hitung y = gx mod p 3. kunci publik A adalah y, sedangkan kunci privat A adalah x

Untuk menandatangani pesan m, A melakukan : 1. 2. 3. 4. 5. 6.

pilih bilangan acak k dengan ketentuan 1 ≤ k ≤ q−1 hitung X = gk mod p dan r = X mod q. Jika r = 0, lakukan langkah 1 hitung k-1 mod q hitung e = SHA-1(m) hitung s = k-1 { e+xr } mod q. Jika s = 0, lakukan langkah 1 tanda tangan A untuk pesan m adalah (r,s)

Untuk memverifikasi tanda tangan A (r,s) pada m, B mendapat salinan sah dari domain parameter A (p,q,g) dan kunci publik y dan melakukan : 1. 2. 3. 4. 5. 6.

verifikasi bahwa r dan s berada dalam interval [1,q-1] hitung e = SHA-1(m) hitung w = s-1 mod q hitung u1 = ew mod q dan u2 = rw mod q hitung X = gu1yu2 mod p dan v = X mod q tanda tangan benar jika dan hanya jika v = r Algoritma DSA

The signature scheme is correct in the sense that the verifier will always accept genuine signatures. This can be shown as follows : From g = hz mod p follows gq ≡ hqz ≡ hp-1 ≡ 1 (mod p) by Fermat's little theorem. Since g>1 and q is prime it follows that g has order q. The signer computes :

Then

Since g has order q we have

Finally, the correctness of DSA follows from

Correctness DSA Algorithm

Halaman

4



Gambar Penggunaan SHA-1 Dengan DSA

Komponen

Deskripsi

Key Generation

Signature Creation

Signature Verification

Tabel Komponen Proses Algoritma DSA

Halaman

5



Implementasi DSA Dalam Matlab Diketahui Plaintext : Tugas Pengganti UTS Oleh Yoga Prihastomo

Gambar Input Plaintext

Gambar Hashed Message Dari Plaintext

Gambar Penentuan Pengunaan Pregenerated Pair

Halaman

6



Gambar Penentuan Pemilihan Pregenerated Primes Pairs

Gambar Pengubahan Pregenerated Primes Pair Ke Biner

Halaman

7



Gambar Generate DSA Parameter

Gambar Proses Signing The Message

Gambar Proses Verifikasi Signature

Halaman

8



Source Code DSA Dalam Pemrograman Java : /* For Genrate Signature */ import import import import import import import import import

java.io.BufferedInputStream; java.io.FileInputStream; java.io.FileOutputStream; java.security.KeyPair; java.security.KeyPairGenerator; java.security.PrivateKey; java.security.PublicKey; java.security.SecureRandom; java.security.Signature;

public class GenSig { public static void main(String[] args) { /* Generate a DSA signature */ if (args.length != 1) { System.out.println("Usage: GenSig nameOfFileToSign"); } else try { /* Generate a key pair */ KeyPairGenerator keyGen = KeyPairGenerator.getInstance("DSA", "SUN"); SecureRandom random = SecureRandom.getInstance("SHA1PRNG", "SUN"); keyGen.initialize(1024, random); KeyPair pair = keyGen.generateKeyPair(); PrivateKey priv = pair.getPrivate(); PublicKey pub = pair.getPublic(); /*Create a Signature object and initialize it with the privatekey*/ Signature dsa = Signature.getInstance("SHA1withDSA", "SUN"); dsa.initSign(priv); /* Update and sign the data */ FileInputStream fis = new FileInputStream(args[0]); BufferedInputStream bufin = new BufferedInputStream(fis); byte[] buffer = new byte[1024]; int len; while (bufin.available() != 0) { len = bufin.read(buffer); dsa.update(buffer, 0, len); } ; bufin.close(); /* Now that all the data to be signed has been read in, generate * a signature for it */ byte[] realSig = dsa.sign(); /* Save the signature in a file */

Halaman

9



FileOutputStream sigfos = new FileOutputStream("sig"); sigfos.write(realSig); sigfos.close(); /* Save the public key in a file */ byte[] key = pub.getEncoded(); FileOutputStream keyfos = new FileOutputStream("suepk"); keyfos.write(key); keyfos.close(); } catch (Exception e) { System.err.println("Caught exception " + e.toString()); } }; }

/* For Test Generating & Testing Signature import import import import import import import

*/

java.io.FileInputStream; java.security.KeyPair; java.security.KeyPairGenerator; java.security.PrivateKey; java.security.PublicKey; java.security.SecureRandom; java.security.Signature;

public class testSig { public static void main(String[] args) { /* Test generating and verifying a DSA signature */ try { /* generate a key pair */ KeyPairGenerator keyGen = KeyPairGenerator.getInstance("DSA"); keyGen.initialize(1024, new SecureRandom()); KeyPair pair = keyGen.generateKeyPair(); /* create a Signature object to use for signing and verifying

*/

Signature dsa = Signature.getInstance("SHA/DSA"); /* initialize the Signature object for signing */ PrivateKey priv = pair.getPrivate(); dsa.initSign(priv); /* Update and sign the data */ FileInputStream fis = new FileInputStream(args[0]); byte b; while (fis.available() != 0) { b = (byte) fis.read(); dsa.update(b); } ; fis.close(); /* Now that all the data to be signed has been read in, sign it */ byte[] sig = dsa.sign(); /* Verify the signature */

Halaman

10



/* Initialize the Signature object for verification */ PublicKey pub = pair.getPublic(); dsa.initVerify(pub); /* Update and verify the data */ fis = new FileInputStream(args[0]); while (fis.available() != 0) { b = (byte) fis.read(); dsa.update(b); } ; fis.close(); boolean verifies = dsa.verify(sig); System.out.println("signature verifies: " + verifies); } catch (Exception e) { System.err.println("Caught exception " + e.toString()); } } } /* Main Program For DSA Algorithm */ import import import import import import import

java.security.KeyPair; java.security.KeyPairGenerator; java.security.PrivateKey; java.security.PublicKey; java.security.SecureRandom; java.security.Security; java.security.Signature;

public class MainClass { public static void main(String args[]) throws Exception { Security.addProvider(new org.bouncycastle.jce.provider.BouncyCastleProvider( )); KeyPair keyPair = generateKeyPair(999); byte[] data = { 65, 66, 67, 68, 69, 70, 71, 72, 73, 74 }; byte[] digitalSignature = signData(data, keyPair.getPrivate()); boolean verified; verified = verifySig(data, keyPair.getPublic(), digitalSignature); System.out.println(verified) ; keyPair = generateKeyPair(888); verified = verifySig(data, keyPair.getPublic(), digitalSignature); System.out.println(verified); } public static byte[] signData(byte[] data, PrivateKey key) throws Exception { Signature signer = Signature.getInstance("SHA1withDSA"); signer.initSign(key); signer.update(data); return (signer.sign()); } public static boolean verifySig(byte[] data, PublicKey key, byte[] sig) throws Exception { Signature signer = Signature.getInstance("SHA1withDSA"); signer.initVerify(key); signer.update(data); return (signer.verify(sig));

Halaman

11



} public static KeyPair generateKeyPair(long seed) throws Exception { Security.addProvider(new org.bouncycastle.jce.provider.BouncyCastleProvider( )); KeyPairGenerator keyGenerator = KeyPairGenerator.getInstance("DSA"); SecureRandom rng = SecureRandom.getInstance("SHA1PRNG", "SUN"); rng.setSeed(seed); keyGenerator.initialize(1024, rng); return (keyGenerator.generateKeyPair()); } }

Source Code DSA Dalam Pemrograman Matlab : % File bin2hex.m For convert Into Binary function yhex = bin2hex(xbin), %Function which takes a binary string and converts to hex string. yhex = ''; for a = 1:4:length(xbin), yhex = [yhex dec2hex(bin2dec(xbin(a:a+3)))]; end % File CreateDigest.m For Create Diggest function [sha] = createdigest(m, varargin); %A function which takes message string, m and creates a message digest %using SHA-1, as described in federal publication FIPS 180-2. %If the message is anything other than a binary string, use the 'convert' %string. e.g. sha = createdigest('abc', 'convert') %If dealing with binary strings, just call the script like this: % sha = createdigest('011000010110001001100011'); %Initial Hash Values %Notation: H[word number](block number) H00=dec2bin(hex2dec('67452301'),32); H10=dec2bin(hex2dec('efcdab89'),32); H20=dec2bin(hex2dec('98badcfe'),32); H30=dec2bin(hex2dec('10325476'),32); H40=dec2bin(hex2dec('c3d2e1f0'),32); %Preprocessing %1) Padding the message

in a 32-bit binary string

%convert message from a message string to a binary string s = ''; if strcmp('convert', varargin) for a = 1:length(m), binstr = dec2bin(double(m(a)), 8); s=[s, binstr]; end else s = m; end %Pad binary string to be a multiple of 512 bits. l = dec2bin(length(s),8); lstring = [int2str(zeros(64-length(l),1))' l]; s = [s, '1', int2str(zeros(mod(448-length(s)-1,512),1))', lstring]; %2) Parsing the padded message

Halaman

12



%Padded message is subdivided into N 512-bit blocks for n = 1:(length(s)/512), eval(['M' int2str(n) '= s(512*(n-1)+1:512*n) ;']); end %Actual Hash Computation for n = 1:(length(s)/512), for t = 1:16, %First 15 32-bit words of the message schedule eval(['Wlog' sprintf('%d', (t-1)) ' = transpose(str2num(transpose(M' sprintf('%d', n) '(32*(t-1)+1:32*t))));']); eval(['W' sprintf('%d',(t-1)) ' = bin2dec(M' sprintf('%d', n) '(32*(t-1)+1:32*t));']) end for t = 16:79, eval(['Wlog' sprintf('%d',t) ' = transpose(circshift(transpose(bitxor(bitxor(bitxor(' 'Wlog' sprintf('%d',t-3) ',Wlog' sprintf('%d',t-8) '),Wlog' sprintf('%d',t-14) '),Wlog' sprintf('%d',t16) ')), -1)) ;']) eval(['W' sprintf('%d',t) ' = bin2dec(transpose(int2str(transpose(Wlog' sprintf('%d', t) '))));']) end %Initializing the five working string variables eval(['a=logical(transpose(str2num(transpose(H0' '))));']); eval(['b=logical(transpose(str2num(transpose(H1' '))));']); eval(['c=logical(transpose(str2num(transpose(H2' '))));']); eval(['d=logical(transpose(str2num(transpose(H3' '))));']); eval(['e=logical(transpose(str2num(transpose(H4' '))));']);

sprintf('%d',

n-1)

sprintf('%d',

n-1)

sprintf('%d',

n-1)

sprintf('%d',

n-1)

sprintf('%d',

n-1)

for t = 0:79, %Setting up the schedule for function f and variable K if (t>=0 & t<=19), f = xor(and(b,c),and(not(b),d)); K=hex2dec('5a827999'); elseif (t>=20 & t<=39), f = xor(xor(b,c),d); K=hex2dec('6ed9eba1'); elseif (t>=40 & t<=59), f = xor(xor(and(b,c),and(b,d)),and(c,d)); K=hex2dec('8f1bbcdc'); elseif (t>=60 & t<=79), f = xor(xor(b,c),d); K=hex2dec('ca62c1d6'); end %Shifting the working variables according to the schedule T=sprintf('%d', [circshift(a(:),-5)';f;e]); T=bin2dec(reshape(T, 3, 32)); T=mod(T(1)+T(2)+T(3)+K, 2^32); eval(['T = mod(T + ' 'W' sprintf('%d', t) ', 2^32);']); T = logical(str2num(dec2bin(T, 32)')'); e = d; d = c; c = circshift(b(:), -30)'; b = a; a = T;

Halaman

13



%debug line %disp(t), disp(dec2hex(bin2dec(int2str(a')'),8)), disp( dec2hex(bin2dec(int2str(b')'),8)), disp( dec2hex(bin2dec(int2str(c')'),8)), disp(dec2hex(bin2dec(int2str(d')'),8)), disp( dec2hex(bin2dec(int2str(e')'),8)) end %Compute the immediate hash value eval(['H0' int2str(n) dec2bin(mod(bin2dec(transpose(int2str(transpose(a)))) sprintf('%d', n-1) ')), 2^32), 32);' ]); eval(['H1' int2str(n) dec2bin(mod(bin2dec(transpose(int2str(transpose(b)))) sprintf('%d', n-1) ')), 2^32), 32);' ]); eval(['H2' int2str(n) dec2bin(mod(bin2dec(transpose(int2str(transpose(c)))) sprintf('%d', n-1) ')), 2^32), 32);' ]); eval(['H3' int2str(n) dec2bin(mod(bin2dec(transpose(int2str(transpose(d)))) sprintf('%d', n-1) ')), 2^32), 32);' ]); eval(['H4' int2str(n) dec2bin(mod(bin2dec(transpose(int2str(transpose(e)))) sprintf('%d', n-1) ')), 2^32), 32);' ]);

+

' = bin2dec(num2str(H0'

+


+


+


+


end blocknum=int2str(length(s)/512); eval(['sha = [H0' blocknum ' H1' blocknum ' H2' blocknum ' H3' blocknum ' H4' blocknum '];' ]); %convert to hexadecimal for testing purposes % H01 = dec2hex(bin2dec(H01)) % H11 = dec2hex(bin2dec(H11)) % H21 = dec2hex(bin2dec(H21)) % H31 = dec2hex(bin2dec(H31)) % H41 = dec2hex(bin2dec(H41)) %useful debug commands %dec2hex(bin2dec(int2str(W15')'),8) % File Dsa.m For DSA Computing %Entire DSA process. %1) generate the primes p and q (generateprimes function) %2) generate private keys x and k, public key y, and g (dsaparams function) %3) signs the message M with the generated DSA parameters (dsasign) %4) verifies that the signature came from the original source (dsaverify) more off; clear all; M='abc'; [p,q, seed, counter] = generateprimes; phex = bin2hex(p); qhex = bin2hex(q); seedhex = bin2hex(seed); seed, counter [x,k,y,g] = dsaparams(p,q); xhex = bin2hex(x) khex = bin2hex(k) [r,s]=dsasign(M,p,q,x,k,y,g); rhex = bin2hex(r) sdex = bin2hex(s) [x, v] = dsaverify(M,r,s,p,q,y,g); if (x == 1), disp('The signature has been verified successfully!')

Halaman

14



else disp('The signature has not been verified') end % File Dsaparams.m For Create Parameter function [x,k,y,g] = dsaparams(p,q), %Generates the rest of the DSA parameters given p and q (which can be %common among a group of users). %x = user's private key, 160 bits long %k = user's private session key, 0
Halaman

15



maple('kinv := k&^(-1) mod q'); maple('r:=(g &^ (k) mod p) mod q'); maple('s:=(kinv*(shaM + x*r)) mod q'); r = maple('r'); s = maple('s'); %r = maple('convert(r , binary, decimal)'); %s = maple('convert(s, binary, decimal)'); % File Dsaverify.m For Verification function [x, v] = dsaverify(M,r,s,p,q,y,g), %Performs the DSA verification process. Returns true if the signed message %is indeed verified to come from the sender with the group's secret [p,q,g] %and the sender's public key y. %Note that r and s have to be passed into this function as binary values %Processing all numbers into decimal for calculations shaM = createdigest(M, 'convert'); shaMdec = maple('convert', shaM, 'decimal', 'binary'); maple('shaM:=', shaMdec); gdec = maple('convert', g, 'decimal', 'binary'); ydec = maple('convert', y, 'decimal', 'binary'); pdec = maple('convert', p, 'decimal', 'binary'); qdec = maple('convert', q, 'decimal', 'binary'); %rdec = maple('convert', r, 'decimal', 'binary'); %sdec = maple('convert', s, 'decimal', 'binary'); maple('r :=', r); maple('s :=', s); maple('g :=', gdec); maple('y :=', ydec); maple('p :=', pdec); maple('q :=', qdec); %Verification Process maple('w := s^(-1) mod q'); maple('u1 := (shaM * w) mod q'); maple('u2 := (r * w) mod q'); maple('v := ((g&^u1) * (y&^u2) mod p) mod q'); v = maple('v'); x = strcmp(r, v); % File Generateprimes.m For Making Primes function [p,q,SEEDbin, counter] = generateprimes(); %Generates the primes p and q as detailed in Federal publication FIPS 186-2 for use in DSA. %Makes extensive use of the maple kernel to generate the seed and test for primes. %p is 1024 bits, q is 160 bits. %Primality tester is already implemented in the maple kernal, %'mhelp isprime' reveals that this is the same algorithm as described on %Appendix 2 of FIPS 186-2. %variables n = 6; %solution to L-1 = n*160 + b, where 0<=b<160 b = 63; %q(160-bits) is generated from this loop. maple('qdec:=4'); maple('readlib(randomize)()'); while strcmp(maple('isprime(qdec)'), 'false'), %Initializing the seed value to be a 2^160 random binary number disp('160 bit prime q has not yet been found. Reseeding: ') SEEDdec = maple('(rand(2^159...2^160)())')

Halaman

16



SEEDbin = maple('convert', SEEDdec, 'binary', 'decimal'); g = length(SEEDbin); %Computing U maple('g:=', g'); maple('SEEDdec:=',SEEDdec); SEED1dec = maple('(SEEDdec+1) mod (2^g)'); SEED1bin = maple('convert', SEED1dec, 'binary', 'decimal'); a = logical(str2num(createdigest(SEEDbin)')'); b = logical(str2num(createdigest(SEED1bin)')'); U = int2str(xor(a,b)')'; %Forming q from U by changing the MSB and LSB to 1. U(1) = '1'; U(length(U)) = '1'; q = U; qlength = length(q); qdec = maple('convert', q, 'decimal', 'binary') maple('qdec :=', qdec); end disp('prime q has been obtained!'); %Generating Vk counter = 0; offset = 2; while (counter < 4096), for k = 0:n, maple('k:=', k); maple('offset:=', offset); temp = maple('convert( ((SEEDdec+offset+k) mod (2^g)), binary)'); eval(['V' num2str(k) '= createdigest(temp);']); end %Generating W from Vk maple('V0 :=', V0); maple('V0 := convert(V0, decimal, binary);'); maple('V1 :=', V1); maple('V1 := convert(V1, decimal, binary);'); maple('V2 :=', V2); maple('V2 := convert(V2, decimal, binary);'); maple('V3 :=', V3); maple('V3 := convert(V3, decimal, binary);'); maple('V4 :=', V4); maple('V4 := convert(V4, decimal, binary);'); maple('V5 :=', V5); maple('V5 := convert(V5, decimal, binary);'); maple('V6 :=', V6); maple('V6 := convert(V6, decimal, binary);'); maple('W := V0 + V1*(2^160)+ V2*(2^(2*160)) + V3*(2^(3*160)) V4*(2^(4*160)) + V5*(2^(5*160)) + (V6 mod (2^63))*(2^(6*160))'); maple('X := W + 2^(1023)'); maple('c := X mod (2*qdec)'); maple('p := X - (c - 1)') plength = length(maple('convert(p,binary)'))

+

if (strcmp(maple('evalb(p < 2 ^ strcmp(maple('isprime(p)'), 'false')), maple('isprime(p)') disp('Rejected p: probably not prime') counter = counter + 1 offset = offset + n + 1 else p = maple('convert(p, binary)'); break; end end disp('prime p has been obtained!');

&

Halaman

(1024))')

,

'true')

17



% File Go.m clc; clear all; more off; disp(' ') disp('WARNING! Generation of the primes p and q take a long time. Using') disp('one of the generated pairs instead would significantly speed up') disp('the verification process.') disp(' '); disp('1) Hash a document or message prior to signing.') M = input('\nPlease input message string to hash:\n> ', 's'); shaMhex = bin2hex(createdigest(M, 'convert')); disp(sprintf('The hashed message is %s', shaMhex)) disp(' ') disp('Strike any key to continue'); pause; clc disp('2) Generate primes p and q, which are public and commonly shared among a group of users.') disp(' This is the trickiest part in the implementation and can take a very long time to complete.') disp(' 3 pairs of prime numbers have already been pregenerated for convenience as per the algorithm') disp(' in FIPS 186-2, Appendix A. The seed and counters have been saved for certifying the proper') disp(' generation of p and q.') disp(' ') answerpq = input('\nGo ahead and generate primes (If you would like to use a pregenerated pair, select n) [y/n] ','s'); if (answerpq == 'y'), [p,q,seed, counter] = generateprimes; phex = bin2hex(p); qhex = bin2hex(q); disp(' '); disp(sprintf('p and q have been obtained: \np = %s \nq = %s', phex, qhex)); disp(sprintf('\nFor certification purposes, the seed and counter values are \nseed = %s \nseed = %d', seed, counter)); else disp(' ') disp('There are currently 3 pairs of pregenerated primes to choose from.'); fid = fopen('primelist.txt', 'r'); while 1 tline = fgetl(fid); if ~ischar(tline), break, end disp(tline) end fclose(fid); inputprime = input('\nWhich pair would you like to use? (Makes no difference, just choose any) [1-3] ', 's'); [p, q, seed, counter] = primelist(inputprime); phex = bin2hex(p); qhex = bin2hex(q); disp(sprintf('\np and q have been obtained: \np = %s \nq = %s', phex, qhex)); disp(sprintf('\nFor certification purposes, the seed and counter values are \nseed = %s \ncounter = %d', seed, counter)); end disp(' ') disp('Strike any key to continue'); pause; clc disp('3) Generating the rest of the DSA parameters:')

Halaman

18



disp(' Once p and q are given, g can be found (g has order q mod has his own') disp(' public key y, and the quadruplet [p, q, g, y] becomes the identity.') disp(' The users private key x and private session key k are making calls') disp(' to the random generator rand, which generates pseudorandom disp(' ');

p). The user users public generated by numbers.')

[x,k,y,g] = dsaparams(p,q); ghex = bin2hex(g); disp(sprintf('Your public group g is \n%s ', ghex)) disp(' ');disp('Generating x, k and y:'); xhex = bin2hex(x); disp(sprintf('\nYour private key x is \n%s ', xhex)) khex = bin2hex(k); disp(sprintf('\nYour private session key k is \n%s ', khex)) yhex = bin2hex(y); disp(sprintf('\nYour public key y is \n%s ', yhex)) disp(' ') disp('Strike any key to continue'); pause; clc disp('4) Signing the message:') disp(' The next step is to sign the hashed message, and this produces the signature pair [r,s].') disp(' ') [r,s]=dsasign(M,p,q,x,k,y,g); rhex = maple('convert', r, 'hex', 'decimal'); shex = maple('convert', s, 'hex', 'decimal'); disp(sprintf('The signature pair [r, s] in integer form is \nr=%s \ns=%s', rhex, shex)) disp(' ') disp('Strike any key to continue'); pause; disp('5) Verifying the signature:') disp(' At this point, the public information of the user, [p, q, g, y], and the signed') disp(' message [M,r,s] is sent to the verifier in an authenticated manner. The verifier') disp(' Then performs a series of steps to prove that the signature was not forged. The') disp(' proof and algorithm for this critical step is documented in FIPS 186-2, Appendix 1.') disp(' ') disp(' '); disp('Beginning the verification process:'); [x, v] = dsaverify(M,r,s,p,q,y,g); if (x == 1), vhex = maple('convert', v, 'hex', 'decimal'); disp(sprintf('v = %s', vhex)) disp('r = v : The signature has been verified successfully!') else disp('The signature has not been verified') end % File Primelist.m function [p,q,seed,counter]=primelist(inputstring); switch inputstring case '1' p = '1110111001110010101101100011111000010110011001000101100010100101011110101100011 00000011100011111100000000110101100110110110001110111001001011000111110000110010 00010000100011110110001010101110000100000111011110100010000110011100000001011000 01110111000000000001100101011111010011101100101111111000000010010010101001001100 11000000111011011011110010010000101101110101101100000111001110110010001110010010 10100011110100110011011110101111101010111010110101010100111100110001110101001101

Halaman

19



01100111001100111101101110111111001101001100000001001100001011110101011111000000 10000000010001111011111001000110000011100001101011011110110100000111010010001010 01000000000011011010011101000011011010011000101000101111010100100110011000000101 10001001011111010100100100000110000100100110001111010001111110011111101110111001 10110011011100010101100111111101001101111011001110111110111110100011011010101110 00101110100100110011000010001001011110010100100010000000101001110110101101110010 10111100000011010100110101100110001101101011111010101100011100111'; q = '1000000010001101101111001101010010111000101110000101101111111111011011010111101 01110100001011110110111101000001110110010100001100100000110111110111101001110100 1'; seed = '1001111111100101110011001001110011100101111110100011011100010001100011000010000 01001000110010011110011011010011010111001100101010001000001111111100100000111010 0'; counter = 504; case '2' p = '1001001011111111101111011010010101000111010000000110110100011001111100100101001 11110101110011101100010101010011110010111000011101000000010101011110101101010001 01111000001101001011101110011010100100100100101010000110011011110110000000111100 11011101110100000011001001011011010100111111111001011000111101100000100101011110 01100111110101010000101110001110111100011001111000001100000101000010101000111110 11011010100110011000111100011000011101000001000101111101000000101011100011100111 10000011100101000000110001101100110000110000000001100111001000001001000100101001 01111101011101101111000010011011111101100010010010000100000111111110000010111000 01100010101001100100110010001001111110100000000001101100000101001011010010100101 01011001011101010011010101110010110001111000111000011000100011100000110100111101 00000111010110011101000010010010001001101111000111111101110001010011001001111110 01010001100101101001111010000110101111100101110110000000110111101110101000011000 11011001101100100101111010111000001001100110000001101110110000111'; q = '1101111100111011100000101001000010110101111011011111111111001010011010111100111 00111011111110011101011111000101001001001100111101011011110100111000101110011101 1'; seed = '1010001100111010111011110011101011011111111001001111000001100000111011000000011 10100100110110000001011111101101101101001010000111100001101010111000011011001001 1'; counter = 252; case '3' p = '1010100001010010100110101000011010101111010000001100100101001111001111101110100 01011011100101011110001100100011001001011111110111000110010000111001000001101010 10001011001010101100010101100110000010001111011001001101001010010111100101001111 11111011111010110111101010000100111001001111111110010100001111000001110110010010 00110001011001111111101110110100110011101011000111010111000001000000010100101011 10011111010011111010000110110010000101100111001111101000110111101010010010101110 10111011011011111111101011100000111110001010100000001100001110001110101100000010 00111111110011110101010101111000101000011111101000100010011110100101010001011101 11100011001010111000000001110000011110010111010110111100101100110011111101100001 00000101110011110100100101000111100011010111010100111110011111110001010111111110 11111110110010001001111100010010001101100011001110010000000010001000110001100111 01010010110101101100110010111001011101000000101110100100000100010001010000101010 01001101111101111000000110100110110101101101011100010000101001111'; q = '1101110001010110010100000010010110101110011100011010001010001100111111100001010 01001011111100110010001100010110110001001010001110000110010101110101011000010000 1';

Halaman

20



seed = '1101001001011011100111001111010011110010001011001110000010100101000101110100000 00111101101000111100101100110100010010100111100011000111010110010011010110110101 1'; counter = 273; otherwise error('selection is out of bounds') end

Referensi Situs :

http://home.pacbell.net/tpanero/crypto/dsa.html

http://javadoc.iaik.tugraz.at/iaik_jce/current/iaik/security/dsa/DSA.html

http://www.unix.org.ua/orelly/java-ent/security/ch10_01.htm

http://www.unix.org.ua/orelly/java-ent/security/ch10_02.htm

http://en.wikipedia.org/wiki/Digital_Signature_Algorithm#Key_generation

http://www.java2s.com/Code/Java/Security/GenerateaDSAsignature.htm

Halaman

21

: Keamanan Sistem Komputer. Digital Signature Algorithm. : Yoga Prihastomo N I M : : Teknik Informatika

Recommend Documents