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
201 views

How to show that the $x^a \equiv 1 \pmod p$ has exactly $\gcd(a,p-1)$ solutions at $Z^*_{p}$?

It is given that $p$ is prime number and $a\ge1$ solution so far: $x^{\gcd(a,p-1)} ≡ 1$ because it known that a group of units of $Z/pZ$ is cyclic and of order $n=p-1$ for $p$ prime, and also in ...
1
vote
1answer
20 views

Probablistic lemma for the Forking Lemma

I am trying to understand the Forking Lemma in cryptography which is a lemma used to prove security of signature schemes by showing that a forging machine can be "forked" (i.e., snapshotted and then ...
1
vote
1answer
29 views

finding $m$ from $c = m^e \pmod{n}$

I'm working through an RSA encryption example, and I'm being asked to solve $c = m^e \pmod{n}$ for $m$ given c, e, and n (along with its factorization.). Since I already have that information ...
0
votes
1answer
49 views

Discrete Logarithm Problem in $GF(p^m)$

I have question regarding DLP in $GF(p^m)$ I know the algorithms for solving the DLP in $GF(p)$ like Baby Step-Giant Step, Pohlig-Hellman etc... But what if we move into the $GF(p^m)$ and are ...
1
vote
2answers
65 views

Discrete log modulo prime

I'm trying to understand properties of the discrete logarithm problem modulo a prime. For a prime $p$, an $\alpha \in \mathbb{Z}_p^*$ and $a \in \mathbb{Z}_{p-1}$ why does $\alpha^x \equiv 1 \mod p$ ...
1
vote
2answers
142 views

RSA - finding $p$ and $q$

If the public key $(e,n)$ and the private key $(d,n)$ are known, how can I find the $p$ and $q$ primes by the easiest way? When $n$ and $\varphi(n)$ are given was easy to solve, but this issue I can't ...
0
votes
1answer
75 views

Public Key Scheme decryption. [closed]

You have been sent a message based on the following Public Key Scheme. 1) Bob chooses two large primes $\ p,q $ with $ p \equiv q \equiv 2 \pmod 3$ and computes $ n=pq. $ 2) Bob chooses integers $ e,d ...
1
vote
0answers
153 views

Solving the discrete logarithm using index calculus, finite fields and factor bases.

(a) Let $p$ be the prime 1073741827, with $\Bbb{F}_p$ the corresponding finite field. A primitive root in $\Bbb{F}_p$ is equal to $g=2$. Use a factor base of primes up to 13 to find the discrete ...
1
vote
1answer
92 views

Proof of an alternative form of Fermat-Euler's theorem.

I want to know a proof of an alternative form of Fermat-Euler's theorem $$a^{\phi (n) +1} \equiv a (mod \; n)$$ when a and n are not relatively prime. I searched some number theory books and a ...
0
votes
0answers
105 views

Factor a big number by Pollard Rho method

How to factor $2^{2^8}+1$ by Pollard Rho algorithm? I have tried this question,but I have no clue. In order to use Pollard Rho, I should know some factor of this number right? But how can I find one?
0
votes
0answers
25 views

How is the table generated for Galois Field?

If I want to generate tables for $01AB\quad 01AB$ for both addition and multiplication, how will it be generated? I am basically confused from this wikipedia example! I hope someone can clear it up ...
-1
votes
1answer
173 views

e * d = 1 mod phi(n); How do I find d? [closed]

given suppose e = 5, phi(n) = 96. How do i find the value of d? How do I solve this problem?
0
votes
0answers
64 views

How to do Rijndael MixColumns step

I am trying to go through all of the the steps in the Rijndael Encryption Algorithm using pencil and paper. I have been using ...
0
votes
2answers
61 views

key generation in RSA cryptosystem: why it can be performed in polynomial time?

Suppose that I want to generate the keys of the RSA cryptosystem: the public key will be the couple $(n,e)$ where $n$ is the product of two primes $p$ and $q$ and gcd$(\phi(n),e)=1$.The private key ...
3
votes
4answers
65 views

choose two prime numbers of length $k$

Maybe the following is a stupid question, if it is I apologize, and I encourage you to close my post. Suppose that I want to encrypt a message with the RSA cryptosystem; the starting rule is the ...
1
vote
1answer
44 views

Schnorr group membership

Consider the multiplicative group of integers modulo $p$ (where $p$ is prime). Suppose this has a subgroup of order $q$ (where $q$ is prime). (Such a subgroup is known as Schnorr group.) Let $0 < ...
0
votes
1answer
50 views

Subadditivity of Entropy

We define $H(X) = -\sum_{x}p_{x}\log p_{x}$ and relative entropy as $H(p(x)||q(x)) = \sum_{x}p(x)\log \frac{p(x)}{q(x)} = -H(X)-\sum_{x}p(x)\log q(x).$ Now we have to prove that $H(X,Y,X) + H(Y) \leq ...
2
votes
1answer
54 views

Finding d in RSA.

Suppose your RSA modulus is $55 = 5 * 11$ and your encryption exponent is $e = 3$. Find the decryption modulus d. I know $d = 40-13 = 27$ However, I get $1$. $$40 = (P_1-1)(P_2-1)$$ extended ...
3
votes
0answers
72 views

RSA-keys are not good?

PK := (n, e) = (1765937, 23755) SK := (n, d) = (1765937, 1734043) Can someone tell me, given these keys, what is not good about them, meaning it should not be very difficult to break it? (Except ...
0
votes
2answers
90 views

To solve for the decryption exponent, why do we solve the congruence $de = 1 (mod (p-1)(q-1))$

So we choose two large primes p and q and multiply them together to get n. We also pick an encryption exponent e and so for any message m, we can compute m^e (mod n) which is our ciphertext c. So ...
1
vote
1answer
30 views

Problem on Miller's Primality test

I am reading Miller's paper entitle "RIEMANN's HYPOTHESIS and Tests for Primality". In the last page, it is defined Dirichlet's L function by $L(S,\chi)=\sum_{n=1}^{\infty} \chi(n)/n^s$ and ...
1
vote
1answer
75 views

Diffie–Hellman key exchange

Today I have learned about primitive roots, as part of my study about Diffie-Hellman, This is the formula: G(generator), P(prime), A(side A), B(side B) A = G^A MOD P B = G^B MOD P AS is a secret ...
0
votes
2answers
50 views

Median primes and cryptography

I've been considering something involving median numbers. If an integer is directly in the middle of two integers, is it possible to accurately extrapolate what two it is between? Can a prime be in ...
0
votes
1answer
115 views

Multiplication-Shift cipher Decyrpt

I am given sets of numbers to decrypt into letters, 446,882,915 ... these are the first 3. So I've been given K=2, a = 68 and shift b = 7. I've been given alphabet of n = 35 symbols. I know the ...
0
votes
1answer
14 views

Is there an equivalent to the DLP with extension fields?

For instance, if I have an extension field of $p^n$, is there a way to recover $p$, other than brute force checking?
1
vote
1answer
64 views

Relation of encryption to P, NP, and NP-Complete

After watching a Harvard Lecture regarding the understanding of P, NP, and NP-Complete,they also talk about our encryption algorithms being cracked or useless once we solve the mathematics side of it? ...
1
vote
2answers
89 views

An “additive” cryptographic hash-function that allows calculating the hash of some data from the hashes of the parts of that data.

I want to use a cryptographic hash-function that allows calculating the hash of some data from the hashes of the parts of that data. This question was already asked on SO - "Additive" hash ...
0
votes
3answers
48 views

RSA decryption problem

(e,n) = (17,323), with ciphertext 185 First compute $\phi(323) = \phi(17*19) = 16*18 = 288$ In order to find the decryption exponent, we must solve 17*d = 1 mod 288 This is equal to $d = ...
0
votes
2answers
64 views

How do I compute Euler phi function efficiently for repeated prime factors?

In RSA decryption problems, you have to compute $\phi(n)$ and then sometimes $\phi(\phi(n))$ quickly. For example, I had to compute $\phi(2^5)$ for one particular problem and it seems to me (for ...
0
votes
2answers
38 views

Requested material on Bilinear Pairing

Bilinear map/pairing is widely used in Pairing based Cryptography. I am new to this area. Can anyone suggest me some good reference on Bilinear pairings? I need at least an example of Bilinear map ...
1
vote
1answer
38 views

Computing fractions Weierstrass curves and DLP problem

I am preparing for a crypto exam by making an old practise exam. I got stuck on the following assignment. I got this weierstrass curve The curve $y^2 = x^3$ is not an elliptic curve over $F_{71}$ but ...
1
vote
1answer
95 views

Finding all Points on a Edwards curve

I need to find all affine points on the Edwards curve: $x^2 + y^2 = 1 - 5x^2y^2$ over $F_{13}$ I tackle this by transforming the equation to: $y^2 = \frac{1-x^2}{1+5x^2}$ I then go from x = 0 to ...
1
vote
2answers
200 views

Number Theory and Cryptography

I am a math tutor at a community college, and I stopped in to ask one of the professors a question about crypto and he lent me a graduate level book on for a full year course in the title of this ...
1
vote
1answer
64 views

Determining if a number is an nth root

I am working on a proof that depends on if an adversary can determine if a number is an $nth$ power for some large prime $p$. My intuition tells me that for a sufficiently large value of $n$ this is ...
2
votes
0answers
35 views

How many commutative block ciphers are there?

Let $K$ and $M$ and be two finite sets. Let $(G,\circ)$ be the group of permutations over $M$ under composition. Let a (implicitly: block) cipher with key in $K$ and message in $M$ be any application ...
1
vote
1answer
36 views

Confused about discrete logarithm question

For purposes of explaining the notation for those unfamiliar, if we fix a prime $q$, as well as $a,b$ nonzero integers $\mod{q}$, $L_a(b) = x$ is the solution to the equation $b = a^x \mod{p}$ We are ...
2
votes
1answer
45 views

Is there a cipher that yields two separate but valid results depending on the key?

Suppose the following. Someone wishes to encrypt a message so it is not intercepted. With traditional ciphers, if the key is guessed correctly, the message is revealed. This cipher is similar– ...
2
votes
1answer
36 views

Decision Diffie Hellman in finite fields

Is there an efficient mathematical algorithm for Decision Diffie-Hellman problem in a finite field $F_q$? I have found a detailed analysis of many more involved or specific cases but nothing on the ...
1
vote
2answers
83 views

Find all $n$ such that if $\gcd(a,n)=1$ then $a^2=1$ mod $n$

I really have no idea where to start with this question: Find all $n$ such that if $gcd(a,n)=1$ then $a^2=1$ mod $n$ I found out that it works for $n = 8$, since all odd numbers modulo 8 have order ...
0
votes
0answers
61 views

RSA Decryption - finding Private Key

Let p and q be primes and $e \in \mathbb{Z}^+$, with $\gcd (e, (p-1)(q-1)) = 1$. Let d be the inverse of $e \mod (p-1)(q-1)$. The decrption process where M is plaintext and C is ciphetext ...
5
votes
2answers
259 views

Understanding Intel's white paper algorithm for multiplication in $\text{GF}(2^n)$?

I'm reading this Intel white paper on carry-less multiplication. For now, suppose I want to do multiplication in $\text{GF}(2^4)$. We are using the "usual" bitstring representation of polynomials ...
1
vote
1answer
24 views

Question regarding Monoalphabetic Phi Test

I've been asked to prove the following system of inequalities; $$1 \ge \phi(T) \ge \frac{n-k}{k(n-1)}$$ Where $\phi(T) = \sum_{i=1}^{k} \frac{n_i (n_i -1)}{n(n-1)}$, $T =$ some text, $n = $ length ...
1
vote
0answers
36 views

statistical analysis of discrete (non-uniform) p-values: cryptographical random data test

i'm doing a statistical analysis of a well-known cryptographic algorithm and have hit an anomaly. i need to prove that what i have found is statistically significant. i am taking block sizes of 256 ...
0
votes
1answer
45 views

For P0 close to P1 the relative entropy can be approximated by its series expansion,Why?

I am reading a article (An overview of distinguishing attacks on stream ciphers, Martin Hell · Thomas Johansson · Lennart Brynielsson) about Distinguishe Attacks. There is a approximate equation ...
0
votes
1answer
57 views

Figuring out RSA Encryption from 1 encrypted and decrypted message

Suppose that you have an encrypted message and a decrypted message (just one). M (the public key) and k (the exponent you raise each number to) are public. Does having one copy both version of a ...
0
votes
0answers
42 views

DLP in a Cyclic group

Let q be a prime. G is a cyclic group of order $q^2$. Show that for solving the DLP in G it's enough to solve two distinct DLPs in two groups of order q . --- We are looking for an x such that ...
0
votes
1answer
32 views

Solving a congruence relation equation

I have the following equation: $$ n \equiv M^a\mod(b) $$ where n, a, b are integers, and M is unknow. How do i solve this equation to find the M value. Those a and b are public keys of the rsa ...
6
votes
0answers
52 views

A special case of zero-knowledge computation

This question is inspired by the disappearance of Malaysian Air 370. Let's suppose the plane crashed into the ocean. These are hotly contested waters where various countries (US, China, India, others) ...
1
vote
1answer
125 views

RSA Ciphertext Message.

Hey I'm really stuck and I have to finish soon. Part A Ray, Sam and Todd are lazy, and they have set up their RSA public keys as $(3,nR),(3,nS),(3,nT)$ respectively. We may assume that any two of ...
1
vote
2answers
77 views

Analyzing and decoding ciphertext

I have a worksheet which contains a dozen ciphertexts where the goal is to decrypt the encrypted English sentence(s). No information is given about what the text contains or what cipher methods are ...