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

learn more… | top users | synonyms

2
votes
1answer
25 views

If the same message is sent to Alice and Bob who are using different public keys, how can somoene following the channel find $m$

Alice and Bob are using different public keys, Alice is using ($N_{1,2}$) and Bob ($N_{2,2}$). A message, $m$ is sent to both of them using their RSA systems. It is also true that $N_1$ and $N_2$ are ...
4
votes
0answers
63 views

Are large prime numbers kept secret? [duplicate]

I've read several times that modern cryptography is based on the fact that multiplying two primes is easy, whereas getting the prime factorization of a random big integer is very hard. (see here) ...
0
votes
1answer
70 views

How to find primitive point on an elliptic curve?

Reading about Elliptic curve cryptography, i came across primitive point's or generator point's but found nothing on how to generate such points any help would be appriciated.
1
vote
1answer
49 views

PowerMod: Solving for the base

Given the problem $c^d \mod n = m$ and values for $d$, $n$, and $m$, how would one solve for $c$? A general solution or approach would be fine, as well as the values for my specific problem are as ...
4
votes
1answer
108 views

Lenstra's Elliptic Curve Algorithm

I am currently trying to understand Lenstra's Elliptic Curve Algorithm for factoring integers. As a source I use "Rational Points on Elliptic Curves" by Joseph H. Silverman and John Tate. They ...
0
votes
0answers
21 views

Permutation certification. A cryptographic hash function for permutations?

Alice has a secret permutation $\alpha$ (a random permutation of an $n$-set; $n=18$ would be a decent choice for the application I have in mind). She wants to convince Bob that she has $\alpha$, but ...
0
votes
2answers
43 views

Factor n=59305397 given that $ p-q \le 10 $

So what is given is that $n=pq\ ; \ p-q = \sqrt{(p+q)^2 -4n} $ Rearranging the $p-q$ equation, I get $$ p+q = \sqrt{(p-q)^2 +4n}$$ So, $$2p = (p+q) + (p-q) \ \text{and} \ q=\cfrac{n}{p}$$ However ...
1
vote
1answer
22 views

Cryptology - Compare the amount of work the cryptanalyst is likely to require - Single vs. Double rotation

"Suppose a cryptanalyst suspects that SECEC SYHRI IRFET SSETE INLST AFNIA FSOAI HFSRT TEATE was obtained by a succession of two rotations with different block lengths and rotation amounts. Compare ...
1
vote
0answers
21 views

What is the algebraic normal form of $F(x,y,z)= Trace (\alpha x^{24}) + x^{312} + yz$?

Let $w$ be a primitive element of $\mathbb F_{5^4}$. Let $\alpha=w^{13}$. Define, $F:\mathbb F_{5^4}\times \mathbb F_{5}\times \mathbb F_{5} \Rightarrow \mathbb F_{5} $ as, $$F(x,y,z)= Tr (\alpha ...
3
votes
1answer
65 views

Permutations: If I know $\alpha$ and the cycle structure of $\alpha\beta$, can I find $\gamma$ for which $\gamma\beta$ also has this cycle structure?

Suppose we have two permutations $\alpha$ and $\beta$ (of a set $S$ of size $|S|=n$), and I know $\alpha$ and the cycle structure of $\alpha\beta$. But I don't know $\beta$. Can I find a ...
-1
votes
0answers
22 views

What is Attribute-Based Encryption?

Can someone kindly guide me from where can I get some simple explanation about attribute-based encryption i.e. aside from the scientific papers? I was searching for a book or something that can help ...
1
vote
1answer
32 views

Find coordinate $y$ of an elliptic curve point

If I have an elliptic curve over a finite filed $F_p$ ($p$ is prime) defined as $$ y^2 \equiv x^3 + ax + b\pmod p,$$ such that $4a^2 + 27b^2 \neq 0$ and suppose I have only given the coordinate $x$, ...
0
votes
0answers
14 views

What is an embedding degree of elliptic curve?

I am dealing with MOV algorithm to transform ECDLP to DLP in $GF(p^k)$, but at the first step I have to determine embedding degree k. I have read the definitions of embedding degree, but still I am ...
3
votes
1answer
45 views

Prove that bitstrings with 1/0-ratio different from 50/50 are compressable

I'm looking for a proof, that $$ \sum_{i=0}^{\lambda n} \binom{n}{i} \le 2^{nH(\lambda)} $$ with $n>0$, $0 \le \lambda \le 1/2$ and $ H(\lambda)=-[\lambda log \lambda + (1-\lambda) log (1-\lambda)] ...
2
votes
1answer
67 views

Primitive polynomials in LFSRs

I need help proving the following theorem. I found it many books but on every single one it says that they omit the proof because it is in every good textbook. THM Let $c(x)$ be a connection ...
0
votes
0answers
24 views

Studying a code in cryptography

So,i'm given a binary code $C$ with it's generator matrix $G=(A,B)$ where $A,B$ are given matrices. The task is to study the code. First question: What does this form $(A,B)$ mean? how would $G$ look ...
0
votes
1answer
25 views

hash function not using bitwise operations

I have a need for implementing an algorithm to validate that a given message is not altered after some operations (for instance after transmission over a medium). A typical way of doing this kind of ...
2
votes
3answers
75 views

can it be proven that something is “difficult” (prime factoring for example)

I understand that the current state of the art suggests that factoring into primes is a difficult problem. I also understand that a large part of public key cryptography seems to be based on that ...
0
votes
1answer
167 views

coding and decoding message with RSA.

First of all, I know how to solve the following exercise; the problem is that there is no solution. "In RSA, Alice chooses $p=53$, $q=63$, public key ($n=3339, e=13$). When Bob sends the message ...
2
votes
1answer
198 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
17 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
26 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
41 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
31 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$ ...
0
votes
2answers
63 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
63 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
53 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
54 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
47 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
19 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
39 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
15 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
48 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
59 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
34 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
37 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
43 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
63 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
33 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
26 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
35 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
1answer
30 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
39 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
43 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
45 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
34 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
35 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
28 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
24 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 ...