Skip to main content
STAGE - Never been refreshed - Debugging On
 
  • CS260: Introduction to Cryptography and Network Security
    0%

Focus Mode is ON. Click ‘X’ at right bottom to close it.

  • Previous
  • Breaking RSA Using Shor's Algorithm
    COURSE INTRODUCTION
    Course Syllabus
    Unit 1: Introduction to Cryptography
    Unit 1 Learning Objectives
    1.1: Introduction to Encryption and Computational Security
    Key Concepts of Cryptography
    How Cryptography Works
    Key Terms for Network Security
    1.2: Block Ciphers vs. Stream Ciphers
    Overview
    More on Stream Ciphers
    1.3: Substitution Cipher
    Basic Techniques
    Python Exercise
    1.4: Transposition Cipher
    Basic Techniques
    1.5: Random Numbers
    The Basics of PRNGs
    Python Example
    1.6: Perfect Secrecy and the One-Time Pad
    Perfect Secrecy a La Shannon
    The Main Idea behind the One-Time Pad
    More on the One-Time Pad
    Unit 1 Assessment
    Unit 1 Assessment
    Unit 2: Hash Functions
    Unit 2 Learning Objectives
    2.1: What Is a Hash Function?
    Overview
    One Way Functions
    Hash Functions
    Python Exercise
    2.2: Collision Resistance
    The Importance of Collision Resistance
    The Vulnerabilities of MD5
    2.3: Merkle-Damgard Construction
    Overview
    Recipes for Hash Functions
    2.4: SHA (Secure Hash Algorithm)
    Overview
    The Security of SHA
    Python Exercise
    2.5: Application: Blockchain
    Introduction to Blockchain
    Proof of Work
    Python Exercise
    Unit 2 Assessment
    Unit 2 Assessment
    Unit 3: Symmetric Encryption
    Unit 3 Learning Objectives
    3.1: Introduction to Symmetric Encryption
    Key Concepts
    3.2: Feistel Cipher
    Combining Transposition and Substitution
    The Elegance of the Feistel Cipher
    3.3: Data Encryption Standard (DES)
    Overview
    Applying the Feistel Cipher
    3.4: Advanced Encryption Standard (AES)
    Beyond DES
    Python Implementations
    3.5: Triple DES (3DES)
    Introduction to 3DES
    Contrasting 3DES with AES
    A Performance Comparison of DES, AES, and DES
    Unit 3 Assessment
    Unit 3 Assessment
    Unit 4: Asymmetric Encryption
    Unit 4 Learning Objectives
    4.1: Asymmetric Cryptosystems
    Introduction to Public Key Cryptography
    4.2: The RSA Cryptosystem
    The RSA Cryptosystem
    4.3: Integer Factorization
    Prime Factorization
    Factoring Techniques
    Python Exercise
    4.4: Congruences Modulo n
    Modular Arithmetic
    More Immersion into Congruences modulo n
    4.5: Euclidean Algorithm
    Computing the GCD
    Python Implementation
    4.6: Inverses Modulo p and the Extended Euclidean Algorithm
    The Extended Euclidean Algorithm
    Python Implementation
    4.7: Fermat's Little Theorem and Its Generalization
    Number Theory for Public Key Cryptography
    4.8: Repeated Squaring Algorithm
    The Basics
    Using Binary Representations
    Python Implementation
    4.9: The RSA (Rivest-Shamir-Adleman) Encryption System
    Some Number Theory
    The RSA Algorithm
    Putting It All Together
    Unit 4 Assessment
    Unit 4 Assessment
    Unit 5: Signatures and Certificates
    Unit 5 Learning Objectives
    5.1: Message Integrity: Authentication, Confidentiality, and Nonrepudiation
    Introduction to IT Security
    5.2: Message Authentication Code (MAC)
    Overview
    Introduction to MAC Architectures and Configurations
    More on MAC Architectures
    5.3: Keyed Hash Functions
    Hash Functions in Authentication
    5.4: Digital Signatures and Certificates
    Overview
    More on Digital Signatures
    Python Implementation
    Unit 5 Assessment
    Unit 5 Assessment
    Unit 6: Key Management
    Unit 6 Learning Objectives
    6.1: Cyclic Groups
    Introduction to Cyclic Groups
    Computational Complexity
    Python Implementation
    6.2: The Discrete Logarithm Problem
    The Discrete Logarithm Problem
    6.3: Diffie-Hellman Key Exchange
    The Diffie-Hellman Algorithm
    Unit 6 Assessment
    Unit 6 Assessment
    Unit 7: Elliptic Curve Cryptography
    Unit 7 Learning Objectives
    7.1: Introduction to Elliptic Curves
    Introduction to the Weierstrass Curve
    Generalizing the Concept of Addition
    Praxis: Evaluating Points on a Curve
    The Details behind Point Addition
    7.2: Group Operations on Elliptic Curves
    Computing Point Addition
    Python Implementation
    7.3: Elliptic Curve Cryptography Applications
    Overview
    Elliptic Curve Diffie-Hellman (ECDH)
    Elliptic Curve Digital Signature Algorithm (ECDSA)
    Python Implementation for ECDSA
    Public Key System Comparisons
    Python Summary
    Unit 7 Assessment
    Unit 7 Assessment
    Unit 8: Zero-Knowledge Proofs
    Unit 8 Learning Objectives
    8.1: Introduction to Zero-Knowledge Proofs
    The Basics
    More Details
    ZKP Adoption and Impact
    8.2: SNARKS
    Overview
    Approaches to ZKPs
    8.3: Application: Ethereum
    Background
    ZoKrates
    Unit 8 Assessment
    Unit 8 Assessment
    Unit 9: Quantum Key Distribution
    Unit 9 Learning Objectives
    9.1: Photon Polarization
    Wave Polarization
    More on Polarization
    Photons
    Photon Polarization
    9.2: BB84 Protocol
    Overview
    The Basics of BB84
    The Details behind BB84
    9.3: Current Technology
    Overview
    The Details behind More Recent Approaches to QKD
    Unit 9 Assessment
    Unit 9 Assessment
    Unit 10: Quantum Algorithms
    Unit 10 Learning Objectives
    10.1: Quantum Operators
    Introduction to Quantum Computation
    Cryptographic Implications
    10.2: Quantum Search Problems
    Overview
    The Deutsch-Jozsa Algorithm and QKD
    Quantum Computing versus AES
    Efficient Quantum Collision Search Algorithm
    10.3: Shor's Algorithm
    Breaking RSA
    Factoring by Perfect Squares
    Overview of Shor's Algorithm
    Shor's Quantum Architecture
    Breaking Symmetric Cryptosystems
    QC Coding Using Cirq
    Breaking RSA Using Shor's Algorithm
    Unit 10 Assessment
    Unit 10 Assessment
    Study Guide
    Course Feedback Survey
    Course Feedback Survey
    Certificate Final Exam
    CS260: Certificate Final Exam
  • Next
  • Course Catalog
    • All categories
    Arts & Humanities
    • Art History
    • Communication
    • English
    • Philosophy
    • Catalyst IT Test
    • Business Administration
    • Computer Science
    • English as a Second Language
    Professional Development
    • General Knowledge for Teachers
    Science and Math
    • Biology
    • Chemistry
    • Mathematics
    • Physics
    Social Science
    • Economics
    • Geography
    • History
    • Political Science
    • Psychology
    • Sociology
  • Home
  • Specialization Programs
    Specialization Programs MBA Degree Program
  • Help
    Getting Started Help Center & FAQ
Close
Toggle search input
You are currently using guest access
Log in
Course Catalog Collapse Expand
  • All categories
Arts & Humanities
  • Art History
  • Communication
  • English
  • Philosophy
  • Catalyst IT Test
  • Business Administration
  • Computer Science
  • English as a Second Language
Professional Development
  • General Knowledge for Teachers
Science and Math
  • Biology
  • Chemistry
  • Mathematics
  • Physics
Social Science
  • Economics
  • Geography
  • History
  • Political Science
  • Psychology
  • Sociology
Home Specialization Programs Collapse Expand
Specialization Programs MBA Degree Program
Help Collapse Expand
Getting Started Help Center & FAQ
Expand all Collapse all
Skip Table of contents

Table of contents

  • Abstract
  • Introduction
    • Our contributions and a summary of our results
    • Notation and conventions
    • On the structure of this paper
  • Our construction
    • Quantum algorithms
    • Reference implementation
    • The quantum Fourier transform
    • The coset representation of modular integers
    • Windowed arithmetic
    • Oblivious carry runways
    • Interactions between optimizations
    • Abstract circuit model cost estimate
    • Approximation error
    • Spacetime layout
    • Runtime
    • Distillation error
    • Topological error
    • Physical qubit count
    • Construction summary
    • Other physical gate error rates
  • Cryptographic implications of our construction
    • Methodology
    • Implications for RSA
    • Implications for finite field discrete logarithms
    • Implications for elliptic curve discrete logarithms
    • On the importance of complexity estimates
    • On early adoption of post-quantum secure schemes
  • Future work
    • Investigate asymptotically efficient multiplication
    • Optimize distillation
    • Optimize qubit encoding
    • Distribute the computation
    • Revisit elliptic curves
  • Conclusion
  1. CS260: Introduction to Cryptography and Network Security
  2. Unit 10: Quantum Algorithms
  3. 10.3: Shor's Algorithm
  4. Breaking RSA Using Shor's Algorithm

Breaking RSA Using Shor's Algorithm

  • Book
  • Print book
  • Print this chapter
Completion requirements
View
This is a book resource with multiple pages. Navigate between the pages using the buttons.

Our construction

 
Back to '10.3: Shor's Algorithm\'
Contact site support
You are currently using guest access (Log in)
Policies
Get the mobile app
Powered by Moodle

© Saylor Academy 2010-2024 except as otherwise noted. Excluding course final exams, content authored by Saylor Academy is available under a Creative Commons Attribution 3.0 Unported license. Third-party materials are the copyright of their respective owners and shared under various licenses. See detailed licensing information. Saylor Academy®, Saylor.org®, and Harnessing Technology to Make Education Free® are trade names of the Constitution Foundation, a 501(c)(3) organization through which our educational activities are conducted.

Privacy Policy Terms & Conditions

Saylor Academy © 2010-2025 except as otherwise noted. Excluding course final exams, content authored by Saylor Academy is available under a Creative Commons Attribution 3.0 Unported license. Third-party materials are the copyright of their respective owners and shared under various licenses. See detailed licensing information. Saylor Academy®, Saylor.org®, and Harnessing Technology to Make Education Free® are trade names of the Constitution Foundation, a 501(c)(3) organization through which our educational activities are conducted.