Questions on cryptography and cryptanalysis, encryption and decryption, and the making and breaking of codes and ciphers.

learn more… | top users | synonyms (2)

2
votes
1answer
45 views

Strong primes in cryptography, their relation to complexity theory and security

According to the lecture slide by Shafi Goldwasser a prime is a strong prime if: $$p = 2q + 1$$ for some prime q. For me it, seems a bit arbitrary that is the definition of a strong prime in ...
8
votes
2answers
458 views

Why is Euler's totient function equal to $(p-1)(q-1)$ when $N=pq$ and $p$ and $q$ are prime in a clean intuitive way?

Why is does euler's totient function equal to $(p-1)(q-1)$ when $N=pq$ and $p$ and $q$ are prime? I had my own proof for it but I really don't like it (it feels not intuitive at all because it ...
0
votes
2answers
77 views

Relating calculus to RSA and/or prime factorization?

I'm writing a math paper on RSA and it would be nice if it had some calculus in it. Is RSA directly related to calculus in any manner? This can include proving theorems, generating keys, or cracking ...
0
votes
2answers
99 views

Define ≡ in this situation?

"Determine $d$ as $d^{-1} \equiv e \bmod \phi(n)$, i.e., $d$ is the multiplicative inverse of $e \bmod \phi(n)$." (number $5$). I'm looking at this, and i'm not sure what the $\equiv$ means in this ...
1
vote
1answer
158 views

Showing (1 - polynomial fraction) raised to a polynomial power is a negligible function

Let $P(k)$ and $Q(k)$ be two polynomials ($k>0$). Let $\mathrm{neg}(k)$ be a negligible function for sufficiently large $k$ (see Appendix on question for definition). Does someone know how to show ...
1
vote
0answers
72 views

Help with Identifying Cipher

Anyone know what type of cipher this might be? 222132143135533 3335521 2214124313 135 35135 353314142412 31253435 313135 1434 2225313554 135 2425333513 351314333545341444 351314333545341444 ...
0
votes
1answer
334 views

Why does RSA have to use Euler's Totient function?

$$\begin{aligned}m^{ed} &\equiv m\bmod n\\ ed &\equiv 1 \bmod \phi(n)\\ \end{aligned}$$ Why does the modulus of the modular multiplicative inverse have to be the totient function? Won't any ...
0
votes
3answers
66 views

Which divisors produce unique moduli? (for RSA encryption)

Sorry if this question is confusing, I'm still confused by the whole thing. I'm trying to understand how RSA encryption works, but I'm having trouble with the modulus part. For RSA to work, $c=m^e ...
2
votes
1answer
38 views

Uniqueness of points in Elliptic Curve addition

When working on a curve E, is the point yielded by P + Q (some P and Q on E) completely unique? What I mean is there are no other points on E sharing the same x or y value. Thanks!
0
votes
1answer
67 views

Find the RSA factorization

I want to solve this exercise: Assume you have to do with an RSA System whose public parameters are (n,e)=(55,17). Now you can compute d. -->That's easy I've got d=33. You know a computer uses CRT ...
0
votes
1answer
62 views

Finding the private key: Attack against El Gamal

El Gamal encryption involves picking $(p,g,b)$ which is our public key. We compute $b=a^x$ $mod$ $p$. Here, $x$ is the private key which we don't know. What are some efficient and strong algorithms ...
1
vote
2answers
66 views

problem about modulus root and quadratic reciprocity

How to calculate $x$ from $x^{14} \equiv 26 \pmod{91}$? What I tried: Let $y=x^2$ $$y^7 \equiv 26 \mod 91$$ then $y \equiv 26 \mod 91$. Then I have $x^2 \equiv 26 \mod 91$ How to solve this? or ...
2
votes
1answer
40 views

RSA cryptosystem with special prime

Let $p < 2^{1000}$ and $q=3 \cdot 2^n - 1$ for $500 < n < 1000$ be primes and set $n=pq$ to be the modulus of the RSA cryptosystem. Find an attack on this system and how many ...
1
vote
0answers
76 views

Given odd number $n$ count the bases to which $n$ is Euler pseudoprime

As the title says we are given an odd number $n$ and wish to find the number of bases $b$ such that $n$ is an Euler pseudoprime; That is, $\gcd(b,n)=1$ and $b^{(n-1)/2} \equiv \left( \frac{b}{n} ...
1
vote
1answer
43 views

RSA modulus and order of multiplicative elements

Given an $n=pq$ where $p$ and $q$ are odd, distinct primes. Let $\alpha \in \mathbb Z_n^*$ and $\text{ord}_n(\alpha)$ be the order of $\alpha$ in $\mathbb Z_n^*$. The text claims that: ...
1
vote
4answers
71 views

What exponent should I raise $26$ to in order to equal $2^{76}$?

I want to figure out how long an all-caps password needs to be to equal $2^{76}$ bits of security. I would type this into Wolfram Alpha, but I'm not sure what function to use or if it can compute ...
1
vote
2answers
49 views

Modulus Function

I am watching a tutorial an i saw how to use the modulus they said if 20/7 = 2.8571422857 you must subtract the whole number then multiply it by the divisor now am trying to understand a Public key ...
1
vote
1answer
99 views

ElGamal like encryption

How can I approach the following exercise: Source: An Introduction to Mathematical Cryptography by Hoffstein This exercise describes an approach similar to ElGamal cryptosystem with a numerical ...
1
vote
3answers
70 views

RSA and phi function

I am in process of writing essay about cryptography and math behind it. I know that φ(n)=(p-1)(q-1), but would it be true if p and q are not primes but just ordinary factors of n?
1
vote
2answers
86 views

Elliptic Curve Crypto

I had just read a primer about ECC, I see how it can be complicated. Something I haven't been able to determine is what information does the client machine get to help decrypt the data? The whole ...
0
votes
2answers
44 views

Confusion regarding the notation used for in the Handbook of Applied Cryptography (integers subtracted from functions, cardinality of functions, etc)

I'm currently reading "The Handbook of Applied Cryptography" (The full textbook is available as pdf documents from that page) and I'm struggling to understand some of the notation in Chapter 2 that's ...
2
votes
1answer
37 views

Given four numbers $(a,b,e,n)$ is it possible to find $k$ such that $k^{e}a = b \pmod n$?

Let $n$ be a large given number. Also, $n = pq$ for some unknown primes $p,q$. The Euler Totient function, $\varphi(n) = (p-1)(q-1)$ is not known or easy to calculate. $e$ is a given number co-prime ...
1
vote
1answer
19 views

Given three numbers $a, b$, and $n$, is it possible to find a number $k$ such that $ka\equiv b\pmod{n}$?

I came up across this problem working on some (purely academic) attack on cryptographic schemes. Given any three integers $a,b,n$ such that $a<n,b<n$, I am interested in an integer $k$ which ...
2
votes
1answer
96 views

Solve $x^2$ $mod$ $23 = 7^2$

What is the procedure to solving $x^2$ $mod$ $23 = 7^2$? According to WolframAlpha, there is no integer solution but I am completely confused as to what steps was taken to determine that. Before ...
0
votes
1answer
836 views

RSA encryption/decryption scheme

I've been having trouble with RSA encryption and decryption schemes (and mods as well) so I would appreciate some help on this question: Find an e and d pair with e < 6 for the integer n = 91 so ...
1
vote
1answer
82 views

Primality test with polynomial congruence (preliminary to AKS algorithm)

I have trouble in understanding the proof of this primality criterion: $n$ is prime if and only if the congruence $(x+b)^n \equiv x^n+b \,\,\,\text{mod} \,n$ holds for every $b\in \mathbb{Z}$. In ...
2
votes
0answers
202 views

Having trouble using the Chinese Remainder Theorem to solve a system of congruences

I'm working on a difficult assignment involving cryptography, and am nearing the end (or so I think). Summed up, I need to solve a system of congruences using the Chinese Remainder theorem. Due to ...
5
votes
3answers
74 views

Public Key Cryptography

Assuming that a message has been sent via the RSA scheme with $p=37$, $q=73$, and $e=5$, what is the decoding of the received message "34?" So far, I have $x^5 \pmod{37\times73} \equiv 34$. How do I ...
1
vote
1answer
195 views

Using euclidean algo to find d (RSA encryption)

The questions says "let p = 5, q =11, n = 55 tocient(n) = 40. e=7. Use the Euclidean algo to find the value of d. This is driving me crazy. Here's what I did: ...
0
votes
1answer
34 views

Non-Negligible function arithmetics

Following the other question: If a function is known to be non-neligible by this definition, (for example $q(x)=1/x$, is it true (provable) that $poly(x)*q(x)$ (for ...
0
votes
1answer
48 views

Negligible function arithmetics

By definition of negligible function, if $q(n)$ is a negligible function, does $poly(n)*q(n)$ is also a negligible function? How can I prove it?
2
votes
1answer
36 views

Solve for a variable in mod

I want to solve for $s=\frac{(M-x^y)}{r}$ mod $(p-1)$ where I know the values for $M,x,y,p,s$ but don't know $r$. How can I solve for $r$? I tried to solve for $r$ by trying to compute ...
6
votes
1answer
89 views

What are the implications of Prime Number Theorem in Cryptography?

I know that primes and prime factorization are the basis concepts in cryptography. However, I would like to know how does the Prime Number Theorem come into picture in cryptography, since it states ...
0
votes
0answers
52 views

how to encrypt “STACK” using RSA with keys $e=133,n=2160$

$n=2257=37\times 61,\phi(n)=2160$ A B C D E F G H I J K $\space $L$\space $ M$\space $ N$\space $ O$\space $ P$\space $ Q$\space $ R $\space $S$\space $ T $\space $U $\space $V$\space $ ...
1
vote
1answer
66 views

El-Gamal: Recovering random number r

For a padded message, M, using the El Gamal encryption schema, how can we determine the random number $r$, when we are given $p$, the prime number, $g$ which is the primitive root of $p$, $b$ and $x$ ...
0
votes
1answer
63 views

RSA Encryption - why does it guarantee a unique cipher?

In RSA encryption, we use $c = M^e (mod N)$ where $(e, N)$ is the public key, $M$ is the plaintext message, and $c$ is the encrypted message or ciphertext. How do we know all message $M$ (for ...
3
votes
1answer
83 views

Probability of an ECM factor

Suppose I have a composite number $N$ divisible by some prime $p\le x.$ What is the probability that one iteration of ECM finds $p$, given parameters B1 and B2? Usually people look for factors in ...
7
votes
0answers
182 views

Homomorphic Compression

Can there be an algorithm such that, given plaintext data P,Q, and compression function e, Such that if we treat P and Q as a number (a series of bits): $$\begin{eqnarray*}e(P + Q)& =& e(P) ...
0
votes
2answers
87 views

Computing p and q from private key

We are given n (public modulus) where $n=pq$ and $e$ (encryption exponent) using RSA. Then I was able to crack the private key $d$, using Wieners attack. So now, I have $(n,e,d)$. My question: is ...
1
vote
1answer
53 views

computing the discrete log of $23^x \equiv 102 \pmod {431}$

I've been working on this problem for a while now. Could someone please help me see where I'm going wrong? "Alice and Bob agree to use a Diffie-Hellman key exchange with values p = 431 and primitive ...
0
votes
3answers
175 views

Coded language puzzle!! [closed]

Here is a puzzle I can't crack. It goes like this: In a certain coded language MANGO=3/5 ORANGE=2/6 APPLE=1/5 Then, POTATO=?? The answer is 5/6. I would like to know to arrive at the answer.
3
votes
0answers
75 views

crack the key or not: generated key

Let $T \in F^{n \times n}$ , $F$ be a field Let $U_1, U_2 \in F^{n \times n}$ be randomly chosen by user 1 resp. user 2. user1 sends $U_1\cdot T$ to user2 , user2 sends $T\cdot U_2$ to user1 . ...
0
votes
0answers
46 views

$c$ primitive root, $a \in \{1,\ldots,p-1\}, w/ j \in \mathbb Z^+, a \equiv c^j \pmod p), a^{\frac{p-1}{2}} \equiv 1 \pmod p\implies j\text{ even}$.

Suppose c is a primitive root modulo $p$. Suppose you have a particular integer $a \in \{1,2,\ldots,p-1\}$ and you have found $j \in \mathbb Z^+$ such that $a \equiv c^j\pmod p$. Show that if ...
1
vote
0answers
101 views

Mathematical foundation crisis and the RSA

I am currently in my last year of high school and I am writing a report on cryptography from a idea historical and mathematical perspective. I am including a few of the subjects: Cantor's diagonal ...
1
vote
1answer
39 views

One-way functions and pseudorandom number generator

Is it true that if there is Cryptographically secure pseudorandom number generator then there is One-way function?
2
votes
0answers
51 views

Queston concerning cracking an RSA message

I don't have a clue how to solve this exercise: Let m be an RSA modulus, g an encryption Exponent and N be a space of Messages. You know that $k^g$ is such that $k \in S \subset N$ with an S of ...
1
vote
1answer
34 views

Good encryption exponent

I have placed a bet that I can create a public key such that my adversary will not be able to crack (decrypt) it for at least one week. For my primes $p$ and $q$, I chose very large numbers that are ...
0
votes
2answers
341 views

What is a perfect square in mod n

I have been stuck with a question on eliptic curves lately. I need to know whether perfect square mod n is different than a normal perfect square. And also is 3 a perfect square in mod 13?
1
vote
2answers
190 views

find the degree of a minimal polynomial for a galois field element in an efficient way (by hand)

I stumbled upon the following question in the problem section of a book on coding theory. A galois field $GF(2^4)$ is constructed as $K[x]$ modulo $1 + x^3 + x^4$ and $\beta$ is the class of $x$, so ...
2
votes
3answers
63 views

computing $2^{170}+ 3^{63}\pmod {19}, 3^{175} + 2^{73} \pmod {17}$, etc… by hand

I came across several questions like this in the problem section of a book on coding theory & cryptography and I have no idea how to tackle them. There must be a certain trick that allows for ...