Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [cryptography]

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

0
votes
1answer
18 views

Centered and bounded implies subgaussian

There's a result that any $B$-bounded centered random variable $X$ (i.e., $\mathbb{E}(X)=0$ and $|X|<B$) is sub-Gaussian with parameter $B \sqrt{2 \pi}$. Does it still true in $n$-dimensions? If ...
0
votes
0answers
17 views

Given the plaintext, is it possible to get the ciphertext given another plaintext-ciphertext pair?

If I have plaintext-ciphertext pairs with the same IV and key, for example for plaintexts 'bob 1' and 'bob 2', and I have a plaintext-ciphertext pair for 'bob 1' with different IV and key... is it ...
2
votes
1answer
48 views

Is wikipedia Pollard's rho algorithm for logarithms wrong?

https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm_for_logarithms I am confused. It seems that algorithms's step x ← r−1(a2i - ai) mod p should be mod ...
0
votes
2answers
30 views

Strictly less then $o$ noation.

We know that $f \in o(n)$ if $f(n)$ is strictly less than $n$, i.e., $\lim_{n}f(n)/n = 0$. What do we mean by saying that $f(n) < o(n)$? Does it means that $f(n) \in o(\sqrt{n})$ for example?
0
votes
0answers
15 views

Build up function for finite field element representation in Magma

Is there a build in function in MAGMA which can represent the element $x\in GF(2^3)$ as $(x_1,x_2,x_3)\in (GF(2))^3$? I need this for the multidimensional Walsh transform.
1
vote
0answers
23 views

Generating random (torsion) point on elliptic curve efficiently

I am looking for an efficient way to generate a random point on an elliptic curve over a finite field, $E(\mathbb{K})$. I know that you can pick a random $x$, compute e.g. in Weierstrass coordinates ...
1
vote
0answers
41 views

Are there any methods for solving numerical triangle? [closed]

There are some numerical triangles such as pascal triangle, https://en.wikipedia.org/wiki/Pascal%27s_triangle or Euler's number triangle, http://oeis.org/wiki/Eulerian_numbers,_triangle_of These ...
3
votes
0answers
29 views

solutions of gold APN functions using trace function

The Gold APN is defined as $F(x)=x^{2^{k}+1}$ in $GF(2^n)$, where $\gcd(k,n)=1$. The differential uniformity computed using $F(x)=F(x+a)=b$ as following: $x^{2^{k}+1} + (x+a)^{2^{k}+1}=b$ $x^{2^{k}+...
1
vote
1answer
34 views

How to solve $x^r [ x^n + 1] = x^{r[n]}$

I send this message to have a piece of advice to solve my problem. Here is the statement: Assume $k$ belongs to $N$ and $GF(2^k)[x]$ is a ring of polynomials with coefficients in the field $GF(2^k)$. ...
1
vote
0answers
41 views

For $n \ge 20$, there are at least $0.6 \cdot \frac{2^n}{n}$ primes in $[2^{n-1},2^n - 1]$.

From the prime number theorem, one can deduce the following inequality: For $x \ge 355991$, if $\pi(x) = |\{p \le x:p \text{ is prime}\}|$ then we have $\frac{x}{ln(x)}\Big(1+\frac{1}{ln(x)}...
0
votes
0answers
19 views

how to find the generator of elliptic curve using matlab

my question is that my Matlab program for elliptic curve generated all points which satisfy the elliptic curve equation now how to find the generator which generates all the points example: ...
0
votes
1answer
50 views

Proof of construction of a matrix

I have a matrix $A=\begin{bmatrix}r_{11}& r_{21} &r_{31}&r_{41}\\ r_{12}&r_{22}&r_{32}&r_{42}\\ r_{13}&r_{23}&r_{33}&r_{43}\end{bmatrix}$, As we see that taking ...
0
votes
0answers
19 views

Combinatorial Optimization of Account Settlement

What are common terminologies for these optimization problems in the literature? Start with N bank accounts having nonnegative integer values. (Ordered integer partition?) At the end of business we ...
1
vote
1answer
25 views

Does $O(log \ n)$ (space) equality testing of $n$-bit integers using $f(x) = x \ mod \ p$ fingerprinting work for negative integers as well?

I found the following lecture from CS271 at UC Berkeley interesting and was taking a look at some of the examples, namely 3.1 on the first page: Link Here is a summary of the problem: Alice has a $n$-...
3
votes
1answer
31 views

solutions of Differentially uniform mappings for cryptography

Kaisa Nyberg provided a proof of number of zeros in inverse mapping in finite field ref. The proof is clear for me except the final step where she proved that the following equation has two solution ...
2
votes
0answers
63 views

Sum of 2 squares implies efficient factorization

I'm concerning myself with factoring semi-primes and believe that if given a large semi-prime ($N$) one finds a non-trivial sum of squares representation: $$ x^2 + y^2 = N$$ Then one can ...
4
votes
0answers
141 views

Analyzing an Obfuscation Algorithm

I'm a software developer, not a mathematician. I saw a question about decoding ciphertext so I'm assuming this is not off-topic in this forum. I have a legacy database that seems to be obfuscated, ...
3
votes
2answers
43 views

Algebraic equation (find $b$ and $c$)

The goal is, given the field extension $\,\mathbb{Q}\subset\mathbb{C}$, to find the minimal polynomial for the element $$\eta=\cos\left(\frac{2\pi}{5}\right)$$ I define the element $$\xi=\cos\left(\...
2
votes
2answers
32 views

Proving exponentiation in $\mathbb{Z}^{*}_{pq}$ is one to one

We saw in our crypto class that in the group $\mathbb{Z}^{*}_{pq}$ where $p$ and $q$ are primes, that if for some $a$, $gcd(a, \phi(pq) = (p-1)(q-1))$ = 1 (where $\phi$ is Euler's totient function) ...
0
votes
0answers
26 views

Encryption using Wavelet transform

I need to know about an article, book or other reference that deals with encryption using Fourier transform and the Wavelet. (I plan to use matlab or other recommended software.)
0
votes
0answers
35 views

reversible modulo equation

I came across an equation regarding some cryptography article that said for each $i$ $z_i= \mod( \lfloor(s_i*f)\rfloor+p_i, f)$ is reversible, i.e given $f, z,s$ we can get back $p$. My question is I ...
1
vote
0answers
29 views

How the multiplication in Ring-LWE is defined?

in the original paper of Ring-LWE (https://eprint.iacr.org/2012/230.pdf), page 18, definition 3.1, they take a cyclotomic ring of integers $R$, and a prime number $q$, and then multiply an element $a$ ...
0
votes
2answers
26 views

Magma function for modulo irreducible polynomial

So, I am trying to make a program in Magma which returns the value table of a given function F over a field $GF(2^n)$. To do so I need a irreducible polyomial. For example, I've considered $GF(2^3)$ ...
1
vote
1answer
84 views

Finding a kernel generator of the dual isogeny

Let's say we have an isogeny $\phi:E\to E/\ker\phi$ between two elliptic curves over some finite field. Let's also assume we know $\ker\phi$ explicitly, or at least a generator of it, e.g. $\langle A\...
-1
votes
1answer
21 views

How many members $a$ in $\Bbb{Z}^*$ have a number $b$, $b^3 = a \pmod n$?

Given two prime numbers $p$ and $q$ such that $3$ does not divide $p-1$ nor $q-1$, and let $pq = n$. How many numbers in $\mathbb{Z}_n^{*}$ (multiplicative group) are equal to some $b^3$ where $b$ is ...
1
vote
1answer
22 views

Dual of generalized Reed-Solomon code

I need to show that $GRS_{n,k}(\alpha,\mathbb{1})^{\perp}=GRS_{n,n-k}(\alpha,\alpha)$, where $\alpha=(1,a,\ldots,a^{n-1})$, $a$ is a primitive $n$-th root of unity, $\mathbb{1}=(1,1,\ldots,1)$. So, ...
0
votes
1answer
58 views

Scalar Point Multiplication for Elliptic Curve Diffie-Hellman Key Exchange

I am trying to understand elliptic curve Diffie-Hellman key exchange and here is a book example which I don't understand. Given values of $G=(2,2)$ and I should calculate $203(2,2)$, which actually ...
1
vote
1answer
63 views

How “deep” is the theory of encryption keys? Can a “generalist” approach it or does one need to be a number theorist? [closed]

How "deep" is the theory of encryption keys? Can a "generalist" approach designing new keys or understanding state of the art "security" or does one need to be a number theorist?
2
votes
2answers
55 views

Let $r$ be primitive root mod $p$. When $x$ goes from $1$ to $p-1$, then $r^x$ (mod $p$) goes through all the numbers $1,\dots,p-1$ in some order

I'm trying to understand this situation. Why do the powers of primitive roots smaller than $p-1$ generate all DISTINCT elements in $\mathbb{Z}_p$? I am aware about what Fermat's little theorem states ...
1
vote
2answers
70 views

Unable to solve this exponential equation - Diffie-Hellman key exchange

By looking at it, I can deduce that $a = 6$, and $b = 5$, but how do I can solve for $a$ and $b$ without guessing? $$2^a = 11b + 9$$
0
votes
0answers
26 views

How do you find log of a Z* number?

I understand modular arithmetic on a base level. I was wondering how can one find log(base 5)20 in Z * base23. I'm very confused about what Z* represents as I've been trying to figure it out for ...
2
votes
1answer
51 views

RSA: Show how to factor $n=pq$, the product of two primes, given $(p-1)(q-1)$

As an exercise in my discrete mathematics textbook, for my first-year course, the following question is asked, on the topic of RSA encryption: Show that we can easily factor $n$ when we know that $n$ ...
1
vote
1answer
34 views

Key Exchange Protocol attack

I am working on the exercise below which ask about whether it is possible to attack the following key exchange protocol on sharing session key $K_s$ between user $X$ and $Y$: $X \rightarrow Y : X \| ...
0
votes
1answer
18 views

Affine cipher with non relatively prime coefficient

The Affine Cipher is to encrypt a message $P$ to a cipher $C$ based on the following rule: $$C\equiv aP + b \pmod {26}, \quad \gcd(a,M) = 1$$ Where the message is a combination of English alphabet....
0
votes
0answers
30 views

Questions on a powerful generalization.

The initial variation was to prove that for $u,v$ two different prime integers such as $\gcd(u,v)=1$ we have $u^{v-1}+v^{u-1}\equiv 1\pmod{uv}$. I solved this question by using the CRT and Fermat ...
1
vote
0answers
20 views

binary montgomery multiplication

In the paper paper-montgomery-multiplication there are a lot of algorithm explained how to make a montgomery multiplication on bit level. But I have problems to understand that correctly. I have ...
0
votes
2answers
28 views

What am I doing wrong decrypting this RSA message?

Here's a basic understanding I have of how RSA works from my notes. Alice generates two primes $p$ and $q$ such that $n= pq$ and finds a $k$ such that $gcd(k,(p-1)(q-1))=1$. She then finds an s ...
1
vote
0answers
62 views

Questions about a proof of the error-bound of the Miller-Rabin-Test

I am trying to understand a proof (from the German book "Einführung in die Kryptografie" by Johannes Buchmann) that there are at most $(n-1)/4$ non-wittnesses against the primality of $n$ in the ...
1
vote
1answer
20 views

Vigenere cipher strength of multiple keys?

If when using a Vignere cipher I replace the key word often with a word earlier in the ciphered plain text would this be stronger due to not being able to do analysis with a repeated key or would it ...
0
votes
1answer
32 views

Hill Cipher and Exponential Cipher Questions

If p = 29, you intercept the message 16 10 10 09 16 02 22 21 21. Try to break the code and read the message, given that ciphertext 16 is plaintext G. (Note: there is more than one possible exponent ...
0
votes
1answer
20 views

Hill cipher: why can the cipher key matrix’s determinant not share common factors with the modulus?

Background The Hill cipher works by: defining a letter-to-number substitution table/list/pattern/etc.; encoding a cypher-word into a column vector $u$ whose components are determined by the said ...
0
votes
1answer
48 views

In the finite field $\mathbb{F}_{101}$ ,where discrete logarithms are $L_2(3)=69$ and $L_2(5)=24$. Compute the discrete logarithm $ L_2(60)$?

Now, I have that $L_2(60)=L_2(4*3*5)=L_2(4)+L_2(3)+L_2(5)=2+69+24=95$. So from my work $L_2(60)$ is $95$, but the answer on some other website gives $14$. I just don't see where I went wrong.
0
votes
0answers
54 views

Cryptography using matrices

I thought about this idea as a method of cryptography. I appreciate if someone could advice if it is wrong. The method applies a SVD (singular value decomposition) method known in the linear algebra. ...
0
votes
1answer
30 views

Impossible ElGamal signatures

From the following problem, I think it is not possible: " You find two signatures made by Alice. You know that she is using the ElGamal signature scheme over $\mathbb{F}_{2027}$. The cyclic group $\...
0
votes
1answer
60 views

Multiplicative inverse of a polynomial in $GF(8)$

I am trying to find the inverse of $x ^3+x +1$ in $GF(8)$. I have done the Euclidean algorithm but I am stuck in the forward process to get the inverse. Please explain how to do it from reverse.
1
vote
1answer
36 views

How to solve RSA without calculator?

I'm trying to create a ciphertext, and I need to solve this congruence: $$ C = 20^{23} \bmod 377. $$ How would I be able to simplify this so that I can do it without a calculator? Since there won't be ...
0
votes
0answers
18 views

BM RSA percolate down problem

I've been going through a paper on Batch Multiply RSA link here. In percolate down step they use r to find the messages by passing the r_l and r_r. When I take an example for messages and work out I ...
5
votes
1answer
111 views

What other uses are there for Prime numbers? [duplicate]

Simple question out of curiosity... Beside the use of cryptographic safety and prime factorization, what other uses are there for prime numbers? Thank you. Edit: To clarify and not confusing with ...
0
votes
0answers
18 views

Message extraction from specific ElGamal encryption system

Suppose you have an ElGamal system over $G=\mathbb{F}_p^* = <g>$ $$\mathcal{E}(k,m)=k^rm$$ $$\mathcal{D}(b,w, x)=wx^{-b}$$ Where the key is $k=y=g^b$, the message is $m$, and where $r$ is a ...
0
votes
1answer
52 views

Frobenius map on elliptic curves over a finite field

Let $E: Y^2=X^3+Ax+B$ be an elliptic curve, defined over $\mathbb{F}_p$ where $p$ is a prime. Define: $$\phi: E(\bar{\mathbb{F}}) \rightarrow E(\bar{\mathbb{F}})$$ by $$\phi(P) = \left\{ \begin{array}...