Questions on cryptography and cryptanalysis, encryption and decryption, and the making and breaking of codes and ciphers.
23
votes
3answers
605 views
What is an elliptic curve, and how are they used in cryptography?
I hear a lot about Elliptic Curve Cryptography these days, but I'm still not quite sure what they are or how they relate to crypto...
21
votes
4answers
2k views
Would a proof to the Riemann Hypothesis affect security?
If a solution was found to the Riemann Hypothesis, would it have any effect on the security of things such as RSA protection? Would it make cracking large numbers easier?
18
votes
2answers
4k views
Why are very large prime numbers important in cryptography?
Firstly, you guys are awesome, and I learn quite a bit just from reading the questions of others.
Secondly, a friend asked me recently why large primes are important for data security, and I was ...
14
votes
3answers
480 views
RSA in plain English
I'm a computer science student, I'm not a mathematician, I don't know anything about number or group theory.
I'm looking at RSA, and I want to understand it.
I know what Fermats's little theorem and ...
14
votes
1answer
855 views
If the abc conjecture has been proven what implication does that have for elliptic curve cryptography?
I am not a mathematician, but I was wondering if the proposed proof of the abc conjecture (PDF) by Shinichi Mochizuki of Kyoto University would contain insights and mathematical tools that would lead ...
12
votes
3answers
273 views
Can we compare two secret numbers?
If you and I each have a secret number, is there a way we can find out whose is larger without either of us revealing our secret number?
Clearly a trusted third party could do the job, but I was ...
11
votes
3answers
170 views
What is necessary to exchange messages between aliens? [closed]
Lets assume that two extreme intelligent species in the universe can exchange morse code messages for the first time. A can send messages to B and B to A, both have unlimited time, but they can not ...
11
votes
5answers
194 views
Why are there$ 736$ $2\times 2$ matrices $(M)$ over $\mathbb{Z}_{26}$ for which it holds that $M=M^{-1}$?
I'm currently trying to introduce myself to cryptography.
I'm reading about the Hill Cipher currently in the book Applied Abstract Algebra. The Hill Cipher uses an invertible matrix $M$ for ...
11
votes
1answer
7k views
Finding a primitive root of a prime number
How would you find a primitive root of a prime number such as 761? How do you pick the primitive roots to test? Randomly?
Thanks
9
votes
5answers
508 views
RSA: is it easy to find the public key from the secret key?
Please answer to my question about RSA, public key cryptosystem.
I know that it is not easy to find the secret key from the public key .
Is it relatively easy to find the public key from the secret ...
8
votes
3answers
862 views
good books on Abstract Algebra and Cryptography for self-study
I want to self-study some abstract algebra and cryptography during the summer, so what are some of books that are suitable for self-study? I have very limited background in algebra and none in ...
8
votes
2answers
169 views
Who is the oldest? (in a non-revealing way)
How can a group of people figure out who is the oldest, without revealing any other information?
Revealing all the ages to a trusted third party is not allowed. Preferably I'm looking for solutions ...
7
votes
3answers
567 views
RSA: How Euler's Theorem is used?
I'm trying to understand the working of RSA algorithm. I am getting confused in the decryption part.
I'm assuming
$$n = pq$$
$$m = \phi(n) = (p - 1)(q - 1)$$
E is the encryption key $\gcd(n, E) = ...
7
votes
2answers
571 views
Is the set of all finite sequences of letters of Latin alphabet countable/uncountable? How to prove either?
Today in Coding/Cryptography class, we were talking about basic definitions, and the professor mentioned that for a set $A=\left \{ \left. a, b, \dots, z \right \} \right.$ (the alphabet) we can ...
7
votes
1answer
1k views
Cracking Playfair code
I need to crack a Playfair encoded text without knowing the keyword. While searching the internet I found a way to do this using a 'shotgun climbing hill' method. Problem is, I can't decide how to ...
6
votes
4answers
515 views
Mental card game
Each of n persons draws a card from a shuffled deck of $k$ cards numbered from $1$ to $k$. There are at least as many cards as persons. The winner is the person who is holding the largest card. If ...
6
votes
3answers
297 views
Does this class of cipher have a name? What weaknesses does it have?
Some Background
In October I have been asked by the school I teach at to organise and lead 'a hands-on cryptography session' for a bright group of 13 year olds to follow a talk on Enigma by an ...
6
votes
2answers
2k views
How can four employees calculate the average of their salaries without knowing other's salary using RSA?
I know of a solution. But this has a limitation that information is partially passed around and there needs some trust level. I'm wondering if any variant of public-private key (e.g. RSA) algorithm ...
6
votes
1answer
295 views
License Plate Statistics
California issues license plates in numeric order (if we turn the letters into numbers). I have fun noticing the latest plate I have seen. I am interested in what you can derive from a series of ...
5
votes
2answers
8k views
How to break XOR cipher with repeating key?
I need to crack a stream cipher with a repeating key.
The length of the key is definitely 16. Each key can be any of the characters numbered 32-126 in ASCII.
The algorithm goes like this:
Let's say ...
5
votes
3answers
596 views
If the Goldbach Conjecture is True, does it make it easier to find large primes?
I was just reading Is every positive nonprime number at equal distance between two prime numbers? (current hot topic) and was reflecting on the fact that computing security (cryptography) is based ...
5
votes
2answers
427 views
Looking for a bijective, discrete function that behaves as chaotically as possible
I need to write a coupon code system but I do not want to save each coupon code in the database. (For performance and design reasons.) Rather I would like to generate codes subsequent that are ...
4
votes
3answers
645 views
Is it possible to guess an AES key from a series of messages encrypted with that key?
I was wondering if it is practically achievable to guess an AES key from a large number of short messages encrypted with that key, the attacker knowing the exact content of every message.
Suppose the ...
4
votes
3answers
326 views
Should RSA public exponent be only in {3, 5, 17, 257 or 65537} due to security considerations?
In my project I'm using the value of public exponent of 4451h. I thought it's safe and ok until I started to use one commercial RSA encryption library. If I use this exponent with this library, it ...
4
votes
2answers
144 views
Diffie–Hellman Problem
I've been reading the Wikipedia Article on the Diffie–Hellman Problem and I've been wondering whether I understood it correctly, because if I did it seems fairly easy to solve.
The Diffie–Hellman ...
4
votes
2answers
202 views
Is the subgroup of quadratic residues modulo $N = pq$ a cyclic group if $p$ and $q$ are primes?
I saw this question When is the group of quadratic residues cyclic? and the answers to that.
I have a similar question. Assume $N=pq$ where $p$ and $q$ are primes. We know that $\mathbb{Z}^*_N$ is ...
4
votes
1answer
85 views
Are there any secure ciphers you can use without a computer?
I have some kids that like encryption schemes such as the Caesar cipher and the Vigenère cipher. I would like to teach them something that's not easily breakable by todays maths and computers, but I ...
4
votes
2answers
78 views
RSA solving for $p$ and $q$ knowing $\phi(pq)$ and $n$
I want to determinate $p$ and $q$ in RSA.
I know that $n = 172451$ and $\phi(n) = 171600$.
$$171600 = pq - (p+q) + 1 = 172451 -(p + q) + 1$$
$$p + q = 172451-171600+1 = 852$$
$$(p-q)^2 = (p+q)^2-4pq ...
4
votes
2answers
203 views
RSA: Creating a key of desired length
Thanks and with respect to the users of this site, I've succeeded in creating an Encryption/Decryption procedure for the RSA algorithm.
I also implemented a Miller-Rabin probabilistic primality test.
...
4
votes
1answer
97 views
RSA Encryption with number theory
I have a number theory class but my professor just put the homework about RSA encryption where we have absolutely no clue how to do, here's the two question, help appreciated:
a) A word has been ...
4
votes
1answer
160 views
Combinatory + Coding Theory
I am reading about an algorithm for finding minimum-weight words in large linear codes. Let $c$ be the codeword of weight $w$ to recover (with size $n$ and in $GF(2)$). Let $N = \left\{1, 2, \ldots, ...
4
votes
1answer
292 views
Generalized Feedback Shift Registers
I find confusing some examples I have seen. Maybe you can help me to determine what is going on with them.
A Generalized Feedback Shift Register (GFSR) sequence defines a sequence $\{W_{i}\}$ ...
4
votes
0answers
45 views
Prove that there are $736$ $2 \times 2$ matrices ($A$) where $A=A^{-1}$ [duplicate]
I'm doing some assignments to teach myself cryptology. I am still at the introductory cryptology level, where a lot of it is discrete mathematics, so I believe - and hope - that it is a somewhat ...
4
votes
1answer
78 views
Does the difficulty of discrete logarithm depend on the difficulty of integer factorization?
The security of many (most? all?) public-key cryptography systems are based on the difficulty of the discrete logarithm or integer factorization. Are these two problems related at all?
With the ...
3
votes
3answers
399 views
Encrypting algorithm
I know there are some encrypting algorithm that once the text (the message) is encrypted there is no way to decrypt it.
I can think one way of doing this: using as encryption key the current date at ...
3
votes
4answers
393 views
Are there “one way” integrals?
If we suppose that we can start with any function we like, can we work "backwards" and differentiate the function to create an integral that is hard to solve?
To define the question better, let's say ...
3
votes
4answers
2k views
Practical method of calculating primitive roots modulo a prime
How are generators of a (large prime) set calculated in popular programs such as pgp and libraries such as java's bouncycastle? i cannot imagine them just churning away at every value between 2 and p ...
3
votes
2answers
196 views
Decryption Problem
The following message was posted in our math department and I wouldn't mind some help into getting started at cracking it:
gectl atnoy danwm etaim oroni snair ohass wveno faome nceto kils
Any ...
3
votes
1answer
451 views
how do I find the prime power decomposition of this number?
I have sat for about 8 hours doing trial and error and I have tried all combinations of different prime numbers but I am totally stuck..
I know that prime power decomposition is suppose to be prime ...
3
votes
2answers
257 views
Elliptic curves over a finite field $\mathbb{F}_p$ where $p$ is prime.
Let $Y^2=f(X)$ be an Elliptic curve over a finite field $\mathbb{F}_p$ where $f(X)=X^3+aX+b$
In an undergraduate coursebook on an Applied Algebra course it states that "It is plausible to suggest ...
3
votes
1answer
149 views
One-time pad without preshared keys
It is my understanding that one-time pad encryption is the only unbreakable encryption, but suffers from the management of huge keys, and the secure distribution of those keys.
Could one-time pads ...
3
votes
1answer
104 views
Distributing letters
I'm trying to distribute Japanese alphabet characters for scrabble game.
Are there any pointers how to do this, the only thing which I know is to make more vowels than consonants.
Any ideas?
3
votes
4answers
260 views
Finite field, I don't quite understand the concept
What is the concept behind AES's finite field? I understand most of you will laugh at my lack of understanding of the concept. I'm trying to learn a greater amount of higher math concepts and I am ...
3
votes
2answers
139 views
How valid is the concern over narrow pipe cryptographic hash function designs?
Narrow pipe hash function designs have recently come under fire, particularly in reference to some SHA-3 candidates. Is this criticism valid? Can it be explained more simply than this paper does?
3
votes
3answers
103 views
3
votes
1answer
185 views
Reference Books on Cryptography
I successfully ended the book Elementary Number Theory by David M. Burton. It is a great book on Number Theory and History of Number Theory. Specially, I loved the concise chapter on Cryptography. ...
3
votes
1answer
133 views
Groups where discrete logarithm is hard
What are examples of groups, where DLP (discrete logarithm problem) is hard?
Two obvious ones are: integers modulo $p$ ($p$ being prime) and elliptic curves over finite fields. What are the others?
3
votes
1answer
336 views
What type of cipher is this?
I've created a type of alphabet cipher in which each character is defined based on how distant it is (in the alphabet) from the preceding character.
So, assuming that A=0, B=1, C=2, etc., and you ...
3
votes
1answer
61 views
Easy way to calculate $614^7 \pmod{2609}$?
We are starting to go over Cryptography in our Number Theory class and we are doing an example of encrypting a message using something similar to RSA method.
I have I need to find what
$$614^7 ...
3
votes
1answer
77 views
Walsh spectrum of a function defined over Galois rings
Let $GR(p^2,m)$ be the Galois ring with $p^{2m}$ elements and characteristic $p^2$. Let $Z^m_{p^2}$ be the cross product of $m$ copies of $Z_{p^2}$ which is the set of integers from zero up to ...
