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

learn more… | top users | synonyms

1
vote
1answer
37 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 ...
1
vote
0answers
43 views
+50

Lenstra's Elliptic Curve Algorithm

I am currently trying to understand Lenstra's Elliptic Curve Algorithm. As a source I use "Rational Points on Elliptic Curves" by Joseph H. Silverman and John Tate. They describe the algorithm as ...
0
votes
0answers
20 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
41 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
63 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
3answers
63 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
1answer
31 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
35 views

LFSR minimal polynomial question

If we have a LFSR, over n(n, Integer), then there is a minimal polynomial by the Cayley-Hamilton theorem, assume the minimal polynomial has coefficients a0-al, l is the max degree of the minimal ...
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 ...
1
vote
1answer
442 views

How to add two points on an elliptic curve

How do you add two points P and Q on an elliptic curve over a finite field $\Bbb F_{p}$. For example: adding the points $(1,4)$ and $(2,5)$ on the curve $y^2 = x^3+2x+2$ over $\Bbb F_{11}$. I know one ...
0
votes
1answer
255 views

RSA and calculating huge exponents

I am writing an Extended Essay on RSA encryption and in the essay, I am going through a worked example of all of the stages involved (key generation, encrypting and decrypting). I am using very small ...
0
votes
0answers
119 views

Knapsack (Merkle-Hellman) find the superincreasing sequence from public key

So here is my problem I know the public key $(9, 11, 13, 17, 18, 36)$ and also the $multiplier:w = 7 ,modulus: m =79$. I want to decrypt the message $(50, 51, 53, 54)$. I am stuck on how to calculate ...
0
votes
1answer
20 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
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
74 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
164 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
29 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
62 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
2answers
77 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 ...
0
votes
1answer
58 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
52 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
53 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
45 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 ...
2
votes
1answer
22 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 ...
2
votes
1answer
43 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– ...
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
votes
1answer
38 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
13 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 ...
3
votes
4answers
58 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 ...
0
votes
2answers
46 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 ...
17
votes
2answers
20k views

Finding a primitive root of a prime number

How would you find a primitive root of a prime number such as 761? How do you pick the primitive roots to test? Randomly? Thanks
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
31 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
25 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
5k views

Matrix multiplication in AES' MixColumns step.

In Advanced Encryption Std, say after a ShiftRow operation, I want to perform MixColumns. State MixColumn ...
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 ...