Tagged Questions

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

learn more… | top users | synonyms

0
votes
0answers
28 views

Infinite One-Time Pad

As you know, when used correctly, a one-time pad allows one to send a message, such that the only thing that can be found out about it is the maximum size (which is also the key length.) It is ...
1
vote
3answers
87 views

Inverse Totient Function, given $n$ find all possible is for $\phi(i)=n$

I am trying to figure out easy understandable approach to given small number of $n$, list all possible is with proof, I read this paper but it is really beyond my level to fathom, attempt for ...
0
votes
2answers
290 views

Cube roots modulo $p$

Let $a$ be a positive integer. Is there any general method of solving equations of the form $$x^3\equiv a$$ modulo $p$, where $p$ is a prime number? Here are two examples: Example 1: In ...
1
vote
0answers
83 views

Rank of Quadratic Form

Let $n,m, s \in \mathbb{Z}$ be integers satisying $n=s^2$ and $m=2n$. Let $\newcommand{\bigmatrix}[1]{ \begin{pmatrix} #1_1 & #1_2 & \cdots & #1_s \\ #1_{s+1} & #1_{s+2} & \cdots ...
0
votes
2answers
113 views

decoding an encrypted text with modulo

A B C D E F G H I J K L M N O 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 P Q R S T U V W X Y Z Ä Ö Ü ß 16 17 18 19 20 21 22 23 24 25 26 27 28 29 00 A encryption method ...
0
votes
1answer
39 views

Modular arithmetic to find the mod of a large number

If $x \equiv 23 \bmod 317$ and $x \equiv 25 \bmod 331$, what is $x \bmod 104927$? What techniques are typically used to solve problems of this nature? It doesn't seem clear to me that it can be solved ...
1
vote
3answers
65 views

Why does a key have to be at least as long as a message (cryptography)?

I am studying cryptography and find it hard to understand. What happens if the key is one bit or 100 bits shorter than the message?
1
vote
1answer
55 views

Can hash function be considered as linear functional?

I'm not very good in functional analysis or cryptography (so I'm not very sure in what I'm saying): A hash function (as I see it) is some kind of rule that makes an integer from an array (of letters ...
2
votes
1answer
238 views

Prove: b passes the Fermat test for $m = p^2$ if and only if $b^{p-1}\equiv 1\pmod {p^2}$

Question: Let $p$ be a prime and $b$ an integer with $\gcd(b,p) = 1$. Prove: $b$ passes the Fermat test for $m = p^2$ if and only if $b^{p-1}\equiv 1\pmod {p^2}$. I know that if $b^{p-1}\not\equiv ...
0
votes
0answers
25 views

Provide sample matrices that could be keys in the Hill cypher

Well, to encrypt some message I need to multiply parts of it by some matrix key, and to decypher it I need to multiply the output by the inverse matrix. But I've found an excercise to provide some ...
0
votes
2answers
126 views

Plaintext attacks: affine cipher

Consider an affine cipher with encryption function $e$, key $k=(k_1,k_2)$ and some prime $p$. The encryption function $e$ is defined as $e(m)=k_1m+k_2$ modulo $p$, where $m$ is some message ...
0
votes
2answers
55 views

Help me come up with a function

I have some numbers and corresponding numbers: 0 = 0 1 = 0 2 = 1 3 = 0 4 = 2 5 = 1 6 = 3 7 = 0 8 = 4 9 = 2 10 = 5 11 = 1 12 = 6 13 = 3 14 = 7 15 = 0 16 = 8 17 = 4 ...
1
vote
0answers
45 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
113 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
43 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
144 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
77 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
38 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
85 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
199 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
37 views

Diffie-Hellman key exchange problem

I would like to ask about a little help about a Diffie Hellman key exchange problem with polynomials. Until now i've solved such problems with numbers, so the algorithm is clear for me. The confusing ...
0
votes
0answers
58 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
79 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
60 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
100 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
67 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
72 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
80 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
58 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
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
421 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
76 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
153 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
71 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
296 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
37 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
66 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
0answers
50 views

Insecure second preimage problem for polynomial hash

Define a compression function $h: \mathbb Z_{2^n} \to \mathbb Z_{2^m}$ (so $n>m$) by: $h(x) = \sum_{i=0}^d a_i x^i \mod \mathbb Z_{2^m}$ where $a_i \in > \mathbb Z$ and $0 \leq i \leq ...
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 ...
0
votes
0answers
48 views

How to determine if an array of digits is random?

Array1: 9999999999... This is not random because its significant deviation from a uniform distribution Array2: 12345678901234567890... This is not random because the distance between two nearest ...
1
vote
0answers
70 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
48 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 ...