Questions on cryptography and cryptanalysis, encryption and decryption, and the making and breaking of codes and ciphers.
3
votes
1answer
77 views
Walsh spectrum of a function defined over Galois rings
Let $GR(p^2,m)$ be the Galois ring with $p^{2m}$ elements and characteristic $p^2$. Let $Z^m_{p^2}$ be the cross product of $m$ copies of $Z_{p^2}$ which is the set of integers from zero up to ...
1
vote
1answer
122 views
maximal algebraic degree of a balanced Boolean functions
While I was studying some cryptography maths, about balanced boolean functions i felt in a proposition that says
...
2
votes
1answer
631 views
Decode the following message which was sent using mod m=7081 and exponent k=1789 (RSA)
Decode the following message which was sent using mod $m = 7081$ and exponent $k=1789$ (RSA):
$$
5192 2604 4222
$$
I solved $\phi(7081)=6912$, and then solved the linear equation $1789u-6912v=1$ where ...
2
votes
0answers
48 views
Are the sets $\left\{\sum_{x \in \operatorname{GR}(p^2,m)}w^{Tr(ax)} \right\}$ and $\left\{\sum_{x \in Z^m_{p^2}}w^{b \cdot x} \right\}$ equal?
Let $GR(p^2,m)$ be the Galois ring with $p^{2m}$ elements and characteristic $p^2$. Let $Z^m_{p^2}$ be the cross product of $m$ copies of $Z_{p^2}$ which is the set of integers from zero up to ...
6
votes
4answers
515 views
Mental card game
Each of n persons draws a card from a shuffled deck of $k$ cards numbered from $1$ to $k$. There are at least as many cards as persons. The winner is the person who is holding the largest card. If ...
1
vote
1answer
674 views
how to find co-prime numbers
Suppose $p$ and $q$ are two prime numbers. How can one quickly calculate how many numbers $x$ there are such that $\gcd(x, (q-1)\cdot(p-1)) = 1$, without using brute force?
2
votes
1answer
48 views
Definition of Bent functions over Galois rings using Fourier transform (walsh transform)
First, note that the following definition is true:
Definition (Carlet): Let $R=GR(p^k,m)$. A function $f$ from $R^n$ to $R$ is bent if
$$|\sum_{x \in R^n} w^{Tr(f(x)-ax)}|=|R|^{n/2}$$
where $a \in ...
4
votes
1answer
97 views
RSA Encryption with number theory
I have a number theory class but my professor just put the homework about RSA encryption where we have absolutely no clue how to do, here's the two question, help appreciated:
a) A word has been ...
2
votes
0answers
38 views
Probability of a characteristic in Blowfish
I'm trying to understand a cryptanalysis of the Blowfish cipher, and I need to calculate the probability of collision in the cipher's S-boxes. Basically an S-box is a list of 256 semi-random 32-bit ...
1
vote
1answer
41 views
Probability of collision in S-box
I'm trying to understand a cryptanalysis of the Blowfish cipher, and I need to calculate the probability of collision in the cipher's S-boxes. Basically an S-box is a list of 256 semi-random 32-bit ...
1
vote
1answer
34 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 ...
11
votes
5answers
194 views
Why are there$ 736$ $2\times 2$ matrices $(M)$ over $\mathbb{Z}_{26}$ for which it holds that $M=M^{-1}$?
I'm currently trying to introduce myself to cryptography.
I'm reading about the Hill Cipher currently in the book Applied Abstract Algebra. The Hill Cipher uses an invertible matrix $M$ for ...
4
votes
0answers
45 views
Prove that there are $736$ $2 \times 2$ matrices ($A$) where $A=A^{-1}$ [duplicate]
I'm doing some assignments to teach myself cryptology. I am still at the introductory cryptology level, where a lot of it is discrete mathematics, so I believe - and hope - that it is a somewhat ...
1
vote
1answer
54 views
How to create 2048 random bits from 256 bits?
Would merely repeating the same value 8 times be sufficient ? Or is there a more clever approach for doing this ? The 256 bit values would be generated from SHA256 of files.
0
votes
1answer
49 views
Find lift($E_{p^2}$) of an elliptic curve $E_p$ defined in field $F_p$ where $p$ is a prime
How to find $E_{p^2}$ of an elliptic curve $E_p$ defined over finite field $F_p$ where $p$ is a prime number?
1
vote
4answers
757 views
Is every encryption a bijective function?
Is there any encryption algorithm that is not bijective function ?
Should an encryption always give the same result given same key ?
-4
votes
1answer
124 views
some discrete mathematic question
The numbers $7$ and $23$ are relatively prime and therefore there must exist integers $a$ and $b$ such that $7a+23b=1$. Find such a pair of integers $(a,b)$ with the smallest possible $a>0$. Given ...
2
votes
2answers
82 views
order of elliptic curve $y^2 = x^3 - x$ defined over $F_p$, where $p \equiv 3 \mod{4}$
It is said that the elliptic curve $y^2 = x^3 - x$ defined over a prime field $\mathbb{F}_p$, where $p \equiv 3 \mod{4}$ has an order $p + 1$.
When I tried to get the elements of $E = \{(x,y) \in ...
1
vote
1answer
56 views
Why just 4 square roots given ($x^2 \bmod N$)
Oblivious transfer algorithm's page on Wikipedia claims:
The receiver picks a random $x$ modulo $N$ and sends $x^2 \bmod N$ to the sender
Note that $\gcd(x,N)=1$ with overwhelming probability, ...
1
vote
1answer
68 views
RSA cryptosystem test question - help please!
Suppose that the 26 symbol alphabet $A,...,Z$ is used for all plaintext and ciphertext messages in an RSA cryptosystem. Suppose also that plaintext message units are length $2$ and ciphertext units ...
0
votes
0answers
20 views
If the plaintext is “HELPMEAR” and the block size is 5, determine the key
We first add on 2 random characters XX to the end to make the number of characters equal to 10.
So we get:
HELPMEARXX
which we can seperate into. (I think)
XXRAE MPLEH
So the key should be 2 ...
0
votes
1answer
39 views
Perfect Secrecy, Encryption
An encryption scheme $(\mathrm{Gen},\mathrm{Enc},\mathrm{Dec})$ over a message space $M$ is perfectly secret if and only if for every probability distribution over $M$, every message $m\in M$, and ...
3
votes
1answer
257 views
Find the Hill cipher key matrix that can realize this permutation
Find the Hill cipher key matrix $K$ that can realize the permutation $$f: (1,2,3,4,5) \to (3,5,1,4,2).$$
I am not sure how to find a $5\times 5$ matrix that satisfies this.
My guess is
...
1
vote
2answers
80 views
Generators of fields, extending groups to fields, finite abelian groups
So I'm working through Koblitz'z "a course in number theory and cryptography" when I came across his proof that every finite field has a generator (ie, There is an element such that the multiplicative ...
1
vote
2answers
43 views
Expectation of characters in a string
What is the expected distance between two ’e’s in a random character stream where ’e’s occur 11% of the time?
0
votes
2answers
51 views
Why is it safe to assume M < all Ns in Håstad's Broadcast Attack
I am reading the Wikipedia article on Broadcast attack. In the prove, the editor made an assumption that M is less than all N. Why is this assumption safe?
2
votes
1answer
82 views
Math refresher that covers several courses?
This is my first post in Mathematics but I'm not new to these forums. I use stakoverflow as I'm in software as a professional. This is going to be long post - not to mention a lot of what may seem a ...
1
vote
3answers
74 views
What course sequence should I study in order to build a foundation for studying cryptography and signal processing?
I studied mathematics about two decades ago, but unfortunately, I remember little of it. I'm hoping to start studying cryptography and signal processing, but I'm not entirely sure what ...
14
votes
1answer
855 views
If the abc conjecture has been proven what implication does that have for elliptic curve cryptography?
I am not a mathematician, but I was wondering if the proposed proof of the abc conjecture (PDF) by Shinichi Mochizuki of Kyoto University would contain insights and mathematical tools that would lead ...
0
votes
2answers
45 views
System of Linear Equations for Congruency
So this is my question:
Find all x such that $4x=3 \pmod{21}$, $3x=2 \pmod{20},$ and $7x=3 \pmod{19}$
So I know I have to use chinese remainder theorem and I know how to do it if $x$ didn't have a ...
1
vote
0answers
34 views
Mathematical Basis of OAuth Encryption
There are numerous explanations of the common public-private key system available online, explaining how large primes are used to encrypt messages. Is there any similar guide to the mathematics of ...
2
votes
2answers
207 views
Cryptography - RSA algorithm - basic question
I have just read a very basic introduction to the RSA algorithm.
Let's suppose my two prime numbers are $p=29$ and $q=37$. Then $n=pq=1073$ and $e=5$. $n$ and $e$ are public.
If I want to send the ...
0
votes
3answers
119 views
Fermat Factorization
Does anyone know how I can use Fermat Factorization to find the two prime factors of the integer $n = pq = 321179$?
I am not sure how to go about solving this and any help would be much appreciated!
0
votes
0answers
48 views
Markov Chain and cryptanalysis
Where I will be able to found papers to read the state-art of the use
that Markov chain in cryptanalysis. I founded this
Canteaut, A. and Chabaud, F. (1998). A new algorithm for finding ...
1
vote
2answers
554 views
Trouble understanding the theory behind negligible functions and their applications in cryptography
I was formally taught that:
$\epsilon$ is a function $\epsilon\colon \mathbb{Z^{\geq0}}\rightarrow \mathbb{R^{\geq0}}$ and if $\exists$d: $\epsilon$ ($\lambda$) $\geq \frac{1}{\lambda^{d}}$ then ...
2
votes
1answer
67 views
System of Linear Equations using Mod
I just want to check that I did a certain problem correctly. This is it:
$$a+b=3 \pmod{26}\\2a+b=7 \pmod{26}$$
Solve for $a$ and $b$
Now I setup the augmented matrix:
$$\left[ \begin{array}{ccc}
1 ...
4
votes
2answers
77 views
RSA solving for $p$ and $q$ knowing $\phi(pq)$ and $n$
I want to determinate $p$ and $q$ in RSA.
I know that $n = 172451$ and $\phi(n) = 171600$.
$$171600 = pq - (p+q) + 1 = 172451 -(p + q) + 1$$
$$p + q = 172451-171600+1 = 852$$
$$(p-q)^2 = (p+q)^2-4pq ...
1
vote
0answers
75 views
Collision resistant hash function
A function is $(\varepsilon, t)$-collision resistant if there is no boolean circuit (using "not", "and", "or") of size at most $t$ which outputs a collision with probability at least $\varepsilon$.
...
1
vote
0answers
99 views
Feasibility of a cryptography transformation
This is a follow-up of the question: Transformation
We are given
$$g^{1/(x+m)},$$
(it is not possible to find $\frac{1}{x+m}$ due to the Discrete log problem), can we find a $k$ such that
...
0
votes
0answers
29 views
How can we determine if two discret logarithms are equal?
Let $p$ be a prime number, and let $g_{1},g_{2},...,g_{n}$ be $n$ generator of $Z^{*}_{p}$, we have a list $y_{1},y_{2},...,y_{n}$ of elements in $Z^{*}_{p}$ such that for every $i\in ...
0
votes
1answer
48 views
Need help finding a blog post
Here are what I remember:
It is either a post on a rather famous blog or maybe an arxiv paper. Pretty sure it was a post.
Regarding the contents (I don't quite remember that well so there might be ...
4
votes
1answer
160 views
Combinatory + Coding Theory
I am reading about an algorithm for finding minimum-weight words in large linear codes. Let $c$ be the codeword of weight $w$ to recover (with size $n$ and in $GF(2)$). Let $N = \left\{1, 2, \ldots, ...
1
vote
1answer
97 views
Question about the meaning of expression in cryptography
Let $G(x)$ be a pseudo-random generator such that:
$G(x)$ = $f_x(0^k)f_x(1^k)$ where $k=|x|$.
I don't understand the meaning of $1^n$, $0^n$ and the differences between them within that ...
1
vote
1answer
133 views
Perfect Secrecy and different probability distributions
M: plaintext space with a probability distribution $P_1$
K: keys space with a probability distribution $P$
probabilities on spaces M and K are independent.
C: cipher text space with an induced ...
2
votes
2answers
226 views
Estimation of factoring time of a $n$-digit number (current state of art) on a desktop
If one should attempt to factorize a number like the RSA-2048, or in general any number with $n$ decimal digits, using the best algorithm available and a modern desktop PC, what is the approximate ...
0
votes
1answer
76 views
Markov Chain + Decoding algorithm
I am ready a paper Canteaut and Chabaud, I don't get understand the values of transition matrix $P$, in the Proposition 4. If, anybody read this paper please help me understand this values: $P_{u,u}$, ...
1
vote
1answer
138 views
Quasi-linear time fully homomorphic encryption using p-adic ring homomorphism
I recently encountered a breakthrough in FHE crypto, which claims to have a literally quasi-linear time FHE without any "lambda" factor in the keys and no noise in the cipher-text.
This fully ...
1
vote
0answers
56 views
A variant of the “closest vector problem” (CVP) in lattice-based cryptography
Consider a public-key scheme on lattices, such as GGH.
The private key is a basis $\mathbf{B} \in \mathbb{Z}^{m \times n}$ of a lattice $\mathcal{L}$ with good properties (such as short nearly ...
1
vote
2answers
106 views
Isomorphism for optimization of GF256 implementation in AES S-Box using intermediary finite fields
I've questions about the implementation of The S-Box in the AES cipher.
In this cipher, the Finite Field GF256 is implemented as a quotient $\mathbb{F}_2[X]/(X^8+X^4+X^3+X+1$).
The operations can be ...
0
votes
1answer
710 views
Matrix multiplication in AES' MixColumns step.
In Advanced Encryption Std, say after a ShiftRow operation, I want to perform MixColumns.
State MixColumn ...
