1 of 14

Lec 1: Class Introduction and Elementary Number Theory

2 of 14

Instructor: Jiayu Xu

  • Fourth-year assistant professor in EECS, main research interest: cryptography
  • xujiay@oregonstate.edu
  • Office hours: Fri 10:00-10:45am, KEC (Kelley Engineering Center) 2021
    • If you have a quick question, you can also send me an email
    • Starting next week

3 of 14

What is this class about??

  • Cryptanalysis: attacks on cryptographic systems
  • This course will focus on cryptanalysis of 2 types of systems
    • RSA “computational number theory”
    • Discrete Logarithm (DL) and its variants “computational abstract algebra”
  • Advanced topic
    • Mostly covers research progress between 1980 and 2010
    • Fast-paced
  • THIS COURSE IS ABOUT BREAKING CRYPTOGRAPHIC SYSTEMS ALGORITHMICALLY, IN A “MATHEMATICAL” SENSE
    • Nothing about implementation
    • No programming

4 of 14

Prerequisites

  •  

5 of 14

Logistics

  • 18-21 lectures, attendance expected
    • If you cannot/don’t want to attend, tell me in advance
  • 3 homework assignments (30%) + 1 presentation (70%)
  • Homework: 1 problem per assignment
    • I tell you where to find solution
    • You summarize it in your own words
    • You can discuss orally but must write up solutions on your own

6 of 14

Presentation

  • Lec 2-7: I talk about RSA cryptanalysis
  • Lec 8-13ish: I talk about DL cryptanalysis
  • Lec 14-20ish: You talk about RSA/DL cryptanalysis
    • 50-80min presentation on 1-3 papers not covered in my lectures
    • I will provide some sample topics in week 3
    • If no time for this: 30-40min presentation (so that 2 presentations can be crammed into 1 class)

7 of 14

Reference books

  • No textbook
  • RSA part heavily relies on Cryptanalysis of RSA and Its Variants by M. Jason Hinek, Chapters 1-6
  • DL part somewhat relies on
    • Algorithmic Cryptanalysis by Antoine Joux, Section 6.4 and Chapter 7
    • Mathematics of Public Key Cryptography by Steven Galbraith, Chapters 13 and 14

8 of 14

  • This is sort of an “experimental” course
    • Not my research area
    • I started learning the materials in Aug 2025…

9 of 14

Elementary Number Theory

10 of 14

Computing GCD

  •  

11 of 14

Euler’s theorem

  •  

12 of 14

Modulo inverse

  •  

13 of 14

Chinese Remainder Theorem (CRT)

  •  

14 of 14

Viewing CRT from a higher angle

  •