Factoring Large Numbers: Stealing Your Secrets

Abstract

The purpose of this research has been to explore the methods and techniques currently used to factor large numbers. The RSA cryptosystem employs large numbers which are the product of two primes to encrypt and decrypt private messages. In order to break these codes, the first step is to factor the large public integer n into its two primes. Although there are many methods to factor these large integers, most are time consuming and may take decades or centuries to complete. The algorithms undertaken in this project are the predominate methods in use today and include the Pollard p-1 and the Quadratic Sieve. These methods are powerful and have the ability to factor large numbers. In order to accomplish these algorithms, the brute force method and the pseudoprime tests must be implemented and they are included in the research as well. The paper includes the methods for an intruder to steal the information sent over insecure lines of communication. In addition, it instructs the order in which the intruder should attempt to break the code, starting with the easiest methods first and then moving to more complicated and time consuming techniques.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 18, 2000
Accession Number
ADA377327

Entities

People

  • Kevin S. Currie

Organizations

  • Air Force Institute of Technology

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Abstracts
  • Air Force
  • Algorithms
  • Composite Materials
  • Computers
  • Cryptography
  • Families (Human)
  • Flight Training
  • Internet
  • Mathematics
  • North Carolina
  • Numbers
  • Operations Research
  • Prime Numbers
  • Security
  • Square Roots
  • Theorems

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Cybersecurity.
  • Strategic Security Studies