Questions on cryptography and cryptanalysis, encryption and decryption, and the making and breaking of codes and ciphers. Consider posting your question at Cryptography.SE.

learn more… | top users | synonyms (2)

-1
votes
3answers
47 views

How do you find the inverse of $17x + 2$, to decode? [closed]

Let's say I'm trying to encode "hi". "h" is $7$ and "i" is $8$. To encode it you do $17(7) + 2 = 119 \pmod {26} = 15$ which is "p", $17(8) + 2 = 138 \pmod {26} = 8$ which is "i". Thus "hi" becomes ...
1
vote
0answers
26 views

Why does RSA fail when p=q [duplicate]

A lot of questions about this have unsatisfying answers that either argues how unsafe RSA is when $p=q$ or points out that $\phi(n) \neq (p-1)(q-1)$ for $p=q$. However, I'd like to know why the RSA ...
2
votes
1answer
39 views

Extended Josephus permutations generated by keyword

The (well known) generalized Josephus algorithm consists in starting from the ordered set $Z_n=\{1,2,...,n\}$, and choosing and removing cyclically from left to right each m-th element until the set ...
2
votes
2answers
75 views

Miller-Rabin primality test for $2^{32}+1$

How can I prove that $2^{32}+1$ is composite number using Miller-Rabin primality test? I can't find a solution which verify the hypothesis of theorem.
1
vote
0answers
26 views

Why is this prime a bad choice for the ElGamal cryptosystem?

Using the ElGamal cryptosystem in $\mathbb{Z}_{p}^{\times}$, the proposed prime is $p = 2^{1947}\cdot 5 + 1$. The exercise asks me to show why this is a poor choice, and I can't quite do it. In my ...
0
votes
1answer
35 views

Struggling to understand argument about number of roots of a polynomial over a field

On a previous Cryptography exam I'm working through, there is the following problem: Given $$f(x) = x^{134}+x^{127}+x^{7}+1$$ and the field $\mathbb{F}_{2^{n}}$ where $n=1463$, how many roots does ...
1
vote
1answer
285 views

How to solve exponential format modular equation have the same base

I'm reading the paper of Taher Elgamal whichs talks about his digital signature scheme. For example a user needs to sign a document $m \in [0, p-1]$ where $p$ is a large prime number. His private key ...
0
votes
0answers
55 views

Group of order $n=pq$

Let $G$ be a group of order $n=pq$, where $p$ and $q$ are prime numbers and let $x$ $\in$ $G$. My question is how hard is to compute $x^{-1}$ in $G$ ?
0
votes
0answers
32 views

Direct sum of two points on an elliptic curve

Given $E:y^{2} = x^{3}+9x$ over $\mathbb{Z}_{71}$, and $A = (0,0), \: B = (1,9)$, I'm asked to find $C=A\oplus B$. I just don't know how the direct sum of two points on an elliptic curve is defined, ...
0
votes
0answers
28 views

Zeta function of $y^2 = x^3 - x$ over Fp

Zeta function of $y^2 = x^3 - x$ over Fp, where p = 3(mod 4) Can someone give an explanation of a zeta function? I've tried researching it, and I cannot seem to understand. Is there some kind of ...
0
votes
0answers
9 views

Application of fixed point theory in cryptography

Does fixed point theory has an application in Cryptography? I really don't know about Cryptography. If you mention any books on this matter it really helpful
1
vote
1answer
18 views

Proof that the group of non-generators in a multiplicative group with a prime order is a sub-group

I'm trying to solve the following problem - Let $\mathbb{Z}^{*}_p$ be a multiplicative group such that $p=2^k+1$ and is prime. I need to prove that the set of elements that are non-generators in ...
1
vote
2answers
71 views

Different heuristics to solve the Caesar cipher

I know two heuristics that can be used to solve Caesar cipher, but I am asked a question in my artificial intelligence class to Give three heuristics that might be used for solving Caesar ...
0
votes
3answers
82 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
53 views

Low public exponent attack in RSA

I am working in RSA. In one exercise I have to perform a low encryption attack for the given data: $e=5$ $n_1=18446744400127067027$ $n_2=18446744374357261961$ $c_1=7487701518489143755$ ...
3
votes
1answer
85 views

Does this approach for factorizing RSA numbers help in any way?

I was thinking about why factorizing RSA numbers is so hard. When humans perform any kind of maths manually, they often employ various 'tricks' that get them closer to the answer. Some are based on ...
0
votes
1answer
30 views

Notation: Meaning of brackets with subscript?

I came across the following expression: $[m + 2r + 2\sum_{i \in S}{x_i}]_{x_0}$. What does the subscripted bracket notation mean? Context: Found in this paper https://eprint.iacr.org/2009/616.pdf. ...
0
votes
1answer
25 views

Compute inverse polynomial over Finite ring

I want to know how to compute this, All this polynomials are over the finite field $\mathbb{F}_{2^8}$. I have that $$ (x^6 + x^4 + x^3)^{-1} \equiv x^4 + x^3 \mod(x^8 + x^4 + x^3 + x + 1) $$ Where ...
0
votes
1answer
220 views

Large sum of 1/GCD's

The problem is related to cryptography, it involves finding the sum of inverse of $GCD$... Say I have an integer $N \leq10^7$, Find sum of all $N/GCD(K,N)...$upto $N$ where $1\leq K\leq N$ Please ...
0
votes
1answer
22 views

Encrypting plaintext with RSA encryption scheme

I have an RSA encryption scheme with parameters $p$ = 31 $q$ = 37 $e$ = 17 I've decrypted the ciphertext $y$ = 2, using CRT and got the following plaintext: $8440 = 721 \pmod{1147}$ Now I ...
1
vote
0answers
35 views

RSA public encryption: Finding p and q given $\phi(pq)$

I have a quick question: My book asks me to show that if someone were to find that value of $\phi(pq)$ then they would be able to find out p and q. Is this possible? I've seen many examples of ...
0
votes
0answers
29 views

Let $m$ be a squarefree odd integer, and let $(a, m) = 1$. Show that $x^2 ≡ a \pmod m$ has a solution if and only if the Jacobian Symbol (a/p) = 1… [duplicate]

Something I have been struggling with! Let $m$ be a squarefree odd integer, and let $(a, m) = 1$. Show that $x^2 ≡ a \pmod m$ has a solution if and only if the Jacobian Symbol $(a/p) = 1$, for all ...
0
votes
1answer
35 views

private key for a secret code“1983”?

Hi !! I tried to find information and examples to solve this RSA cryptography with public and private keys problem but couldn't find it.. This is my preparation questions for exam and not ...
2
votes
2answers
97 views

Irreducibility of $x^3 − a$ over the field of $q$ elements

I have done much research on this specific question. I have come across many different theorems and definitions on this topic. However, I am having difficulties piecing them together to create a nice ...
2
votes
1answer
29 views

Congruence relation I'm having trouble with

I have this specific congruence relation, and although solving it with a calculator is trivial, I'd like to know what strategy I can use to solve this by hand. The relation is $79^7 \equiv x \mod ...
0
votes
1answer
39 views

Equation for largest text-block size mod n in RSA encryption

I am working on a small program in sage that encodes messages using RSA encryption in an attempt to show the process step by step, along with mathematical justifications for each step, for a ...
0
votes
1answer
49 views

Number of Points on an Elliptic Curve

If I have an elliptic curve $$E: y^2 = x^3 + bx + c$$, with $b, c$ integers mod some prime $p$. And $x^3 + bx + c$ has at least one root mod $p$. How can I show that the number of points on the ...
0
votes
0answers
19 views

Need clarity on calculating the y coordinate in elliptic curve cryptography

I'm just new to elliptic curve cryptography. I have been working on RSA for quite some time. Moreover I'm not from a mathematical background. The whole concept looks very complex. So tell me my ...
2
votes
1answer
41 views

What do modern day cryptographers work on? [closed]

I am a student of Pure Mathematics.I want to get some information on the following: $1$.What do modern day cryptographers work on? $2$. How does pure mathematics influence modern day cryptography? ...
0
votes
2answers
214 views

The oringinal massage in the RSA cryptosytem and coded massage both are the number in [0, n-1]

The actuall message M in the RSA system can be any number between 0 and n-1. The coded message R is also a number between 0 and n-1, but can it be any such number? I am litlle confuse about the ...
0
votes
0answers
24 views

I choose $n$ words from $k$ randoms words from a dictionary with $t$ words. How much entropy is this password?

Let's say I have a dictionary of $t$ words. I randomly select a set of $k<t$ words (no duplicates). Next, I deterministically choose $n<k$ words from those $k$ words (say, pick the first $n$ ...
1
vote
0answers
29 views

How can I explain a Zero Knowledge Proof with minimal mathematics

I asked this earlier on how to explain a Zero Knowledge Proof to a layman. but I'm looking for a mathematical analogy that might "enhance" the superpower explanation. In that linked superpower, that ...
0
votes
0answers
25 views

Attack El Gamal private key when p is composite

I'm supposed to find private key of El Gamal cypher. I have public key ($p,g,h$) and order of the element g ($q$). $$h = g^x\ mod\ p$$ ($x$ = private key) I have figured out that $p$ is composite, ...
5
votes
1answer
75 views

pseudo-primality and test of Solovay-Strassen

Let $n$ be an odd integer, we say that $n$ is $a$-pseudoprime if $gcd(a,n)=1$ and : $$\begin{pmatrix}\frac{a}{n}\end{pmatrix}=a^{\frac{n-1}{2}}\text{ mod } n $$ Euler's criterion states that if $n$ ...
0
votes
1answer
70 views

An encoding of non - empty sequence of strings

An exercise problem $:$ Let $\Sigma = \left\{a, b, c, d, e\right\}$ be an alphabet. We define an encoding scheme as follows: $g(a) = 3, g(b) = 5, g(c) = 7, g(d) = 9, g(e) = 11$. Let $p_i$ denote ...
-1
votes
1answer
39 views

What's the maximal number of q-arrays of $A_7(7,d)?$

$ A_q(n, d) $ is the maximum number of a $q$-arrays of length n and minimum distance at least d. What's the best known exact values of $ A_7(7,d)$ for $d=1$ to $7$?
1
vote
3answers
44 views

Use Fermat's Little Theorem to prove $24^{31} \equiv 23^{32} \mod{19}$

I'm trying to prove $24^{31} \equiv_{19} 23^{32}$. All I have so far is that this is equivalent to $23^5 \equiv_{19} 24^6$ by multiplying both sides by $24^623^5$. I can see that there seems to be ...
0
votes
1answer
38 views

Understanding Quadratic Residue Modulo n Structure

Quadratic Residue Modulo n: $a \in \mathbb Z_n^*$ is quadatic residue of modulo n if there exists an element $x \in \mathbb Z_n^*$ such that $$x^2 \equiv a \mod n$$ I'm not getting the intuition ...
0
votes
0answers
15 views

Find the 9Bit key for a 3 round toy DES cipher

Differential Analysis I am having a difficult time to understand and find a solution to the key. As you might have noticed the last 6 digits (000 111) of the plain text are same. All the below ...
0
votes
2answers
45 views

Cryptography: Solve x² ≡ 331 (mod 385) using congruencies

How can I find (3) congruence equations to solve $$x^2\equiv331\pmod{385}$$ using Legendre and Jacobi Symbols and use the Chinese Remainder Theorem to combine the solutions to those equations to ...
2
votes
2answers
76 views

RSA and extended euclidian algorithm

I'm learning about RSA, public private key stuff, and I just found a very nice article explaining the basics. ...
0
votes
0answers
28 views

Finding generator for El Gamal cryptosystem

I am working with the prime p = 503 I know about the algorithm where you find the factors of (p-1), which in this case are 1,2,251 and 502. Then i tried to randomly select an integer from g ...
3
votes
2answers
97 views

Understanding Carmichael Number

A Carmichael number is a composite number $n$ which satisfies the modular arithmetic congruence relation $$a^{n-1} \equiv 1 \pmod n$$ $\forall a \in \mathbb Z_n$ such that $\gcd(a, n) = 1$ Wiki says ...
0
votes
1answer
27 views

cWhat is the importance of Multiplicative Group in Number Theory

I'm studying Number theory basics for Cryptography Course. There is a term called Multiplicative Group which confuses me litle bit I know $|\mathbb Z_n^*| = \phi(n)$ (Euler Phi Function) and ...
2
votes
1answer
89 views

RSA when N=pq and p = q

I was curious what's to happen when $p = q$ for $N=pq$ in RSA scheme. First I realize that one can easily find out $p$ and $q$ by taking a square root of $n$. However, it appears to me that under ...
0
votes
0answers
10 views

Determine if an algorithm has solutions or not

I m actually studying Turing works concerning Enigma's machine. Actually, I am wondering if it does exist anything, an algorithm or something that allows people to tlel if an algorithm can be break ...
4
votes
2answers
46 views

Find element with order 12 of multiplicative group using CRT

I have been stuck on this question for a long time and don't really understand how the Chinese remainder the is related to the order of a unit. Use the Chinese Remainder Theorem to find an element ...
0
votes
0answers
35 views

What is the advantage or disadvantage of Pollards rho algorithm compare to Parallel Substitution or Quantum Algorithm?

I’m trying to combine the two algorithms but for the mean time I want to know your opinion or suggestion. I use my spare time to create a Pollards rho algorithm using basic formula in spreadsheet to ...
0
votes
1answer
21 views

Question related to the security of RSA method

I learned about the RSA method, where if B wants to send a message $M$, say $0 \leq M <n = pq$ to A with public key $(n,e)$, then B sends $M'= M^e (mod \ n)$. Then A can decode this message using ...
5
votes
3answers
817 views

Which background is more suitable to study “Cryptography” [closed]

I am a student of Pure Mathematics and also interested in programming .I have learnt C++,SAGE . Recently I have started learning "Cryptography" .But there are many definitions involved here like ...