An Analysis of Algorithms for Solving Discrete Logarithms in Fixed Groups

Abstract

Internet protocols such as Secure Shell and Internet Protocol Security rely on the assumption that finding discrete logarithms is hard. The protocols specify fixed groups for Diffie-Hellman key exchange that must be supported. Although the protocols allow flexibility in the choice of group, it is highly likely that the specific groups required by the standards will be used in most cases. There are security implications to using a fixed group, because solving any discrete logarithm within a group is comparatively easier after a group-specific precomputation has been completed. In this work, we more accurately model real-world cryptographic applications with fixed groups. We use an analysis of algorithms to place an upper bound on the complexity of solving discrete logarithms given a group-specific precomputation.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 2010
Accession Number
ADA518636

Entities

People

  • Joseph Mihalcik

Organizations

  • Naval Postgraduate School

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Asymetric Encryption
  • Computer Network Security
  • Computer Networks
  • Computer Science
  • Cryptography
  • Hash Tables
  • Information Processing
  • Mathematics
  • Network Protocols
  • Network Science
  • Number Theory
  • Numbers
  • Secure Communications
  • Security Protocols
  • Standards
  • Transport Protocols

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Calculus or Mathematical Analysis
  • Computer Networking