Number Theory Commons^™

The Vulnerabilities To The Rsa Algorithm And Future Alternative Algorithms To Improve Security, James Johnson

Cybersecurity Undergraduate Research Showcase

The RSA encryption algorithm has secured many large systems, including bank systems, data encryption in emails, several online transactions, etc. Benefiting from the use of asymmetric cryptography and properties of number theory, RSA was widely regarded as one of most difficult algorithms to decrypt without a key, especially since by brute force, breaking the algorithm would take thousands of years. However, in recent times, research has shown that RSA is getting closer to being efficiently decrypted classically, using algebraic methods, (fully cracked through limited bits) in which elliptic-curve cryptography has been thought of as the alternative that is stronger than …

Provably Weak Instances Of Plwe Revisited, Again, Katherine Mendel

CSB/SJU Distinguished Thesis

Learning with Errors has emerged as a promising possibility for postquantum cryptography. Variants known as RLWE and PLWE have been shown to be more efficient, but the increased structure can leave them vulnerable to attacks for certain instantiations. This work aims to identify specific cases where proposed cryptographic schemes based on PLWE work particularly poorly under a specific attack.

Probability Distributions For Elliptic Curves In The Cgl Hash Function, Dhruv Bhatia, Kara Fagerstrom, Max Watson

Mathematical Sciences Technical Reports (MSTR)

Hash functions map data of arbitrary length to data of predetermined length. Good hash functions are hard to predict, making them useful in cryptography. We are interested in the elliptic curve CGL hash function, which maps a bitstring to an elliptic curve by traversing an inputdetermined path through an isogeny graph. The nodes of an isogeny graph are elliptic curves, and the edges are special maps betwixt elliptic curves called isogenies. Knowing which hash values are most likely informs us of potential security weaknesses in the hash function. We use stochastic matrices to compute the expected probability distributions of the …

The Generalized Riemann Hypothesis And Applications To Primality Testing, Peter Hall

University Scholar Projects

The Riemann Hypothesis, posed in 1859 by Bernhard Riemann, is about zeros
of the Riemann zeta-function in the complex plane. The zeta-function can be repre-
sented as a sum over positive integers n of terms 1/ns when s is a complex number
with real part greater than 1. It may also be represented in this region as a prod-
uct over the primes called an Euler product. These definitions of the zeta-function
allow us to find other representations that are valid in more of the complex plane,
including a product representation over its zeros. The Riemann Hypothesis says that
all …

Modern Cryptography, Samuel Lopez

Electronic Theses, Projects, and Dissertations

We live in an age where we willingly provide our social security number, credit card information, home address and countless other sensitive information over the Internet. Whether you are buying a phone case from Amazon, sending in an on-line job application, or logging into your on-line bank account, you trust that the sensitive data you enter is secure. As our technology and computing power become more sophisticated, so do the tools used by potential hackers to our information. In this paper, the underlying mathematics within ciphers will be looked at to understand the security of modern ciphers.

An extremely important …

Secure Multiparty Protocol For Differentially-Private Data Release, Anthony Harris

Boise State University Theses and Dissertations

In the era where big data is the new norm, a higher emphasis has been placed on models which guarantees the release and exchange of data. The need for privacy-preserving data arose as more sophisticated data-mining techniques led to breaches of sensitive information. In this thesis, we present a secure multiparty protocol for the purpose of integrating multiple datasets simultaneously such that the contents of each dataset is not revealed to any of the data owners, and the contents of the integrated data do not compromise individual’s privacy. We utilize privacy by simulation to prove that the protocol is privacy-preserving, …

Quantum Attacks On Modern Cryptography And Post-Quantum Cryptosystems, Zachary Marron

Senior Honors Theses

Cryptography is a critical technology in the modern computing industry, but the security of many cryptosystems relies on the difficulty of mathematical problems such as integer factorization and discrete logarithms. Large quantum computers can solve these problems efficiently, enabling the effective cryptanalysis of many common cryptosystems using such algorithms as Shor’s and Grover’s. If data integrity and security are to be preserved in the future, the algorithms that are vulnerable to quantum cryptanalytic techniques must be phased out in favor of quantum-proof cryptosystems. While quantum computer technology is still developing and is not yet capable of breaking commercial encryption, these …

The Rsa Cryptosystem, Rodrigo Iglesias

Williams Honors College, Honors Research Projects

This paper intends to present an overview of the RSA cryptosystem. Cryptosystems are mathematical algorithms that disguise information so that only the people for whom the information is intended can read it. The invention of the RSA cryptosystem in 1977 was a significant event in the history of cryptosystems. We will describe in detail how the RSA cryptosystem works and then illustrate the process with a realistic example using fictional characters. In addition, we will discuss how cryptosystems worked prior to the invention of RSA and the advantage of using RSA over any of the previous cryptosystems. This will help …

Efficiently Representing The Integer Factorization Problem Using Binary Decision Diagrams, David Skidmore

All Graduate Plan B and other Reports, Spring 1920 to Spring 2023

Let p be a prime positive integer and let α be a positive integer greater than 1. A method is given to reduce the problem of finding a nontrivial factorization of α to the problem of finding a solution to a system of modulo p polynomial congruences where each variable in the system is constrained to the set {0,...,p − 1}. In the case that p = 2 it is shown that each polynomial in the system can be represented by an ordered binary decision diagram with size less than 20.25log₂(α)³ + 16.5log₂(α)² + …

Cayley Graphs Of Semigroups And Applications To Hashing, Bianca Sosnovski

Dissertations, Theses, and Capstone Projects

In 1994, Tillich and Zemor proposed a scheme for a family of hash functions that uses products of matrices in groups of the form $SL_2(F_{2^n})$. In 2009, Grassl et al. developed an attack to obtain collisions for palindromic bit strings by exploring a connection between the Tillich-Zemor functions and maximal length chains in the Euclidean algorithm for polynomials over $F_2$.

In this work, we present a new proposal for hash functions based on Cayley graphs of semigroups. In our proposed hash function, the noncommutative semigroup of linear functions under composition is considered as platform for the scheme. We will also …

Counting Solutions To Discrete Non-Algebraic Equations Modulo Prime Powers, Abigail Mann

Mathematical Sciences Technical Reports (MSTR)

As society becomes more reliant on computers, cryptographic security becomes increasingly important. Current encryption schemes include the ElGamal signature scheme, which depends on the complexity of the discrete logarithm problem. It is thought that the functions that such schemes use have inverses that are computationally intractable. In relation to this, we are interested in counting the solutions to a generalization of the discrete logarithm problem modulo a prime power. This is achieved by interpolating to p-adic functions, and using Hensel's lemma, or other methods in the case of singular lifting, and the Chinese Remainder Theorem.

Statistical Analysis Of Binary Functional Graphs Of The Discrete Logarithm, Mitchell Orzech

Mathematical Sciences Technical Reports (MSTR)

The increased use of cryptography to protect our personal information makes us want to understand the security of cryptosystems. The security of many cryptosystems relies on solving the discrete logarithm, which is thought to be relatively difficult. Therefore, we focus on the statistical analysis of certain properties of the graph of the discrete logarithm. We discovered the expected value and variance of a certain property of the graph and compare the expected value to experimental data. Our finding did not coincide with our intuition of the data following a Gaussian distribution given a large sample size. Thus, we found the …

Deconstructing The Welch Equation Using P-Adic Methods, Abigail Mann, Adelyn Yeoh

Mathematical Sciences Technical Reports (MSTR)

The Welch map x -> g^x-1+c is similar to the discrete exponential map x -> g^x, which is used in many cryptographic applications including the ElGamal signature scheme. This paper analyzes the number of solutions to the Welch equation: g^x-1+c = x (mod p^e) where p is a prime, and looks at other patterns of the equation that could possibly exploited in a similar cryptographic system. Since the equation is modulo p^e, where p is a prime number, p-adic methods of analysis are used in counting the number of solutions modulo p …

Deconstructing The Welch Equation Using P-Adic Methods, Abigail Mann, Adelyn Yeoh

Rose-Hulman Undergraduate Research Publications

The Welch map x -> g^x-1+c is similar to the discrete exponential map x -> g^x, which is used in many cryptographic applications including the ElGamal signature scheme. This paper analyzes the number of solutions to the Welch equation: g^x-1+c = x (mod p^e) where p is a prime, and looks at other patterns of the equation that could possibly exploited in a similar cryptographic system. Since the equation is modulo p^e, where p is a prime number, p-adic methods of analysis are used in counting the number of solutions modulo p …