| Bibliografi |
|
| Pengarang |
| Pusaka Kaleb Setyabudi; |
| Barcode |
|
| Cat. Karya |
|
| No. Induk |
|
| Pembimbing |
| Lim Yohanes Stefanus |
| Kata Kunci |
| General Number Field Sieve, integer factorization |
| Pembimbing 3 |
|
| Pembimbing 2 |
|
| Tahun buku |
| 2017 |
| Barcode RFID baru |
| 11603638 |
| Tahun Angkatan |
| 2017 |
| Progam Studi |
| Ilmu Komputer |
| Lokasi |
| FASILKOM-UI; |
| Tanggal Datang |
| 31/01/2017 |
| Abstrak Indonesia |
| ABSTRAK
Nama : Pusaka Kaleb Setyabudi
Program Studi : Ilmu Komputer
Judul : Faktorisasi Integer Besar dengan Algoritma Number Field
Sieve untuk Aplikasi Kriptografik
Faktorisasi integer adalah salah satu hal yang menjadi perhatian dalam bidang
kriptografi karena menjadi salah satu fondasi keamanan dalam dunia digital.
Belum adanya solusi yang efisien terhadap faktorisasi integer menjadi salah satu
alasan diciptakannya beberapa skema dan protokol keamanan yang bergantung
pada tingkat kesulitan faktorisasi integer besar seperti pembuatan digital signature
dan sistem enkripsi-dekripsi kunci publik RSA. Hingga saat ini, beberapa
algoritma faktorisasi integer dengan kompleksitas waktu sub-eksponensial telah
diciptakan, seperti Quadratic Sieve dan General Number Field Sieve (GNFS).
Pada tugas akhir ini, dilakukan penelaahan dan implementasi terhadap algoritma
faktorisasi integer GNFS, serta faktorisasi terhadap beberapa integer semiprime
(biprime) besar. Untuk memahami General Number Field Sieve diperlukan pemahaman
terkait pengetahuan lain seperti aljabar abstrak dan teori bilangan pada kriptografi,
seperti aritmetika modular dan residu kuadratik. Program hasil implementasi
General Number Field Sieve dibuat dengan menggunakan bahasa pemrograman
Python versi 3.3.5 dan dieksekusi pada sistem berprosesor Intel R! CoreTM
i7 4720HQ dengan 4 core (8 logical core) @ 2.6GHz, RAM 12 GB, dan dengan
sistem operasi Ubuntu 16.04.1 LTS. Beberapa strategi telah diterapkan untuk
mempercepat faktorisasi dengan algoritma GNFS seperti penyesuaian (tuning)
terhadap parameter-parameter bebas dalam GNFS, penggunaan struktur data
yang lebih efisien untuk menyimpan matriks biner, serta pemanfaatan komputasi
secara paralel. Meski demikian, beberapa bagian implementasi belum memanfaatkan
metode yang paling optimal karena keterbatasan pemahaman untuk menggunakan
metode tersebut, salah satunya adalah pemanfaatan algoritma Lanczos
dalam mencari solusi nontrivial dalam sistem kongruensi linier. Program hasil
implementasi mampu memfaktorkan integer semiprime (biprime) dengan 40 digit
yaitu 2630492240413883318777134293253671517529 dalam waktu 23 menit 19
detik. Sebagai pembanding, algoritma Trial Division tidak mampu mendapatkan
faktor dari integer tersebut dalam batas waktu 4 jam.
Kata Kunci:
faktorisasi integer, General Number Field Sieve |
| Daftar Isi |
|
| Cat. Umum |
|
| Judul |
| Faktorisasi interger besar dengan algoritma number field sieve untuk aplikasi kriptografik |
| Asal |
|
| Korporasi |
|
| NPM |
| 1306398945 |
| Abstrak English |
| ABSTRACT
Name : Pusaka Kaleb Setyabudi
Program : Computer Science
Title : Large Integer Factorization using Number Field Sieve Algorithm
for Cryptographic Applications
Integer factorization is one of the main attention on the field of cryptography because
it is used as one of the foundation of digital security. The absence of an
efficient solution to integer factorization is one of the reason why there are security
protocols/schema that are built and depend on the difficulty of big integer factorization
such as digital signature and RSA public key encryption-decryption system.
Until now, some integer factorization algorithms with subexponential time complexity
have been made, such as Quadratic Sieve and General Number Field Sieve.
In this final project, GNFS algorithm for integer factorization is studied and implemented,
and used to factorize some semiprime (biprime) integers. To understand
General Number Field Sieve algorithm, some knowledges are needed such as abstract
algebra and number theory related to cryptography (e.g., modular arithmetic
and quadratic residue). The program was built using Python 3.3.5 and executed on
a system with Intel R!CoreTM i7 4720HQ dengan 4 core (8 logical core) @ 2.6GHz
processor, RAM of 12 GB, and Ubuntu 16.04.1 LTS as the operating system. Some
strategies are used in order to optimize time and memory performance of the program
such as tuning on the free parameters of GNFS algorithm, use of efficient data
structure to store binary matrices, and utilization of parallel computing. However,
some parts of the are not implemented using the most optimal method/algorithm
such as the use of Lanczos algorithm to find nontrivial solutions of a system of
linear congruences. The program can factor a semiprime (biprime) integer with
40 digits (2630492240413883318777134293253671517529) in 23 minutes and 19
seconds. As a comparison, Trial Division algorithm cannot factorize the same integer
within four hour time limit.
Keywords:
General Number Field Sieve, integer factorization |
| Pengarang 2 |
|
| Subjek |
|
| Penguji 2 |
| Ari Saptawijaya |
| Penguji 3 |
|
| Pembimbing 1 |
|
| Fisik |
| xii, 85 hlm.;ill; 30 cm |
| Bahasa |
| Ind |
| Lulus Semester |
|
| Penerbitan |
| Depok: Fakultas Ilmu Komputer UI, 2017 |
| No. Panggil |
| SK-1495 (Softcopy SK-977) |
| Penguji 1 |
| Amril Syalim |
| Lulus semester SI |
|