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

learn more… | top users | synonyms (2)

1
vote
0answers
48 views

Closest vector problem

Given is a vector $v=\begin{pmatrix}2,&-1,&0,&1\end{pmatrix}$ as the shortest vector of the lattice $\Lambda (B)$, where $B$ is determined as $B=\begin{pmatrix}4 &-3 & 2 & 0\\ ...
1
vote
4answers
116 views

Using Euler Totient to compute digits in $3^{40000005}$

I'm trying to computer the two rightmost digits in $3^{40000005}$. Can this be done using the Euler Totient function alone as: For every digit $m >1$, $$m = \prod_{i = 1}^{n}p_i^{e_i}$$ where the ...
3
votes
1answer
44 views

Why is the RSA exponentiation function a permutation (i.e. a bijection) over $\mathbb{Z}^*_N$

Why is the RSA exponentiation function a permutation (i.e. a bijection) over $\mathbb{Z}^*_N$? My doubt was specifically why, when raising to the power of the decryption key d we get a unique number ...
1
vote
1answer
146 views

How do I row reduce a matrix mod 26 when it is singular mod 26?

Cryptography assignment question: matrix $A$ is \begin{equation} A = \left(\begin{array}{ccc} 1 & 0 & 0 \\ 1 & 3 & 1 \\ 0 & 2 & 5 ...
0
votes
1answer
35 views

Periodic streams

I have problems proving the following result; Suppose you have two periodic streams $x_n$ with period $M$ and $y_n$ with period $N$. The streams $x_n+y_n$ and $x_n y_n$ are periodic with periods ...
0
votes
1answer
83 views

how to show a function is negligible

Let neg(x) be a negligible function. Let p be a polynomial function such that p(k)≥0 for all k>0. What can we say about f = neg(p(k))? Is f a negligible function? If yes, then is there ...
0
votes
0answers
39 views

enumerating in pseudo random order - version 2

edit 2: what kind of statistical test do I need to get an idea of the randomness of the order of a list? The list contains all base-4 numbers from 0000 to 3333 exactly once. edit 1: I've added ...
0
votes
1answer
88 views

enumerating in pseudo random order

edit 3: After more testing, I asked a new question with a jsfiddle enumerating in pseudo random order - version 2 edit 2: It's not a multiplication. It's more like a maze. A given column in row 1 ...
3
votes
0answers
219 views

Bachelor Thesis - Galois Theory Research Topics?

I'm on the last semester of my bachelor's degree (undergrad degree) and I will be writing my thesis next semester. I have talked to a professor at my university and one of the topics he suggested was ...
0
votes
0answers
64 views

Using knapsack problem for digital signatures

Is it possible to use the knapsack problem for digital signatures? What I am imagining is something like the Merkle–Hellman knapsack cryptosystem, but used for digital signing, rather than encryption. ...
1
vote
2answers
84 views

Determine a generator of $\mathbb{Z}^*_{11}$ manually.

What is the best/standard way to do this manually? Could you describe a solution in a step-by-step fashion.
2
votes
1answer
62 views

Determine the number of divisors in $K[x]$ of $1 + x^{15}$ and of $1+x^{120}$

where $K[x]$ is the set of all polynomials where coefficients are elements of $K$ $(0,1)$ Is this related to the problem of finding how many cyclic linear codes there are if $n = 15$ and $120$? I've ...
0
votes
1answer
111 views

ElGamal Public Key Cryptosystem and Digital Signature Scheme

I'm tryting to understand how ElGamal algorithm works, and I got the following example, and I couldn't understand one part of this: A) P=23, g=5. B) x=3, then y=10 (for 53 mod 23=10 ). C) Sign for ...
2
votes
2answers
72 views

Manually performing the Miller-Rabin probabilistic primality test

What is the standard/best way to do that manually? Could you give an example with $n=241$ and $a = 3$.
1
vote
1answer
76 views

Manipulating square roots mod p (prime) and when is $g^{ \frac{x}{2}} = p - z_1 \pmod p$ true?

tl;dr: If $z_1 = g^t \pmod p$ is one of the square roots of $g^x \pmod p$ such that $ \frac{p-1}{2} \leq t < p-1$. Then, does $p-z_1 = g^{\frac{x}{2}} \pmod p$ hold true? Say that we define a ...
0
votes
2answers
82 views

Explanation of $d^{-1}$ in modular arithmetic [duplicate]

I wasnt quite sure what to name this question, so that's what it is. I'me working on an encryption system, and I need modulus. I already asked a question on this, here, and I cannot figure out the ...
0
votes
2answers
63 views

How to make RSA function injective

I'm trying to make the RSA function $ F(c) = m^e \mod n $ injective (ie, always generates a unique value for $ c $ / don't repeat values in set $ C $). Through some research, I've found this is ...
2
votes
1answer
47 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
472 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
78 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
100 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
161 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 ...
1
vote
1answer
354 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
67 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
39 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
69 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
66 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
67 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
41 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
88 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
44 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
72 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
50 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
101 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
76 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
88 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
45 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
39 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
20 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
110 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
847 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
84 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
210 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
75 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
226 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
35 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
50 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
91 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 ...