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

learn more… | top users | synonyms

2
votes
2answers
101 views

Why modular arithmetic in secret sharing?

I learned about how secret sharing works in my math class today. From what I understand about the way I was taught it's possible to implement it, I can choose a secret number $N$ and generate a ...
1
vote
0answers
62 views

Asymmetric block ciphers?

Any block cipher transforms a block of $N$ bits into another block of $N$ bits based on a $\mathcal{K}$ bit key. This can be considered to be a substitution cipher on an alphabet consisting of $2^N$ ...
0
votes
0answers
24 views

how does this informal proof show a particular PKE scheme is secure against non-adaptive memory attacks?

On pg. 5 of this paper the author does a section on the "Idea of the proof" using a technique known as dimension reduction. The actual proof is on pg. 13 Section 3.1 of the same paper. However, I am ...
1
vote
1answer
68 views

What is the difference between $O(N/ \log_2(N))$ and $N-o(N)$?

On the second page of this paper under the introduction section they say "We first show that for the set of parameters considered by [16], the function family has $O(N/ \log_2(N))$ simultaneously ...
0
votes
1answer
154 views

Cryptography textbook

Might come as a rather strange request but does anyone know a textbook on cryptography that is small and short, say around 300 pages max. I am tired of having a sore shoulder from carrying 5 heavy ...
1
vote
0answers
76 views

Decryption of an Encrypted Message

Suppose we are given sending a message to two people: A and C. A and C have the same RSA encryption modulas: R=(some arbitrary number, say) 454564515456465465465156. But A and C have two different ...
2
votes
1answer
78 views

Problem about primitive root

Let p be a prime such that $q = \frac{p − 1}{2}$ is also prime. Suppose that g is an integer satisfying $g \not\equiv \pm 1 \pmod p$ and $g^q \not\equiv 1 \pmod p$. Prove that g is a primitive root ...
0
votes
1answer
121 views

Primitive Root Theorem

Let $p$ be a prime and let $q$ be a prime that divides $p − 1.$ (a) Let $a \in F_p$ and let $b = a^{\frac{p−1}{q}}$. Prove that either $b = 1$ or else $b$ has order $q.$ (Recall that the order of $b$ ...
2
votes
1answer
89 views

Modular exponentiation WITHOUT modular exponentiation

Given that 719 is prime, find the least positive residue of $11^{721} (mod\ 719)$, without using modular exponentiation. So, I know how to use modular exponentiation and have done it to get the ...
0
votes
0answers
53 views

Hash functions that produce a point on an elliptic curve.

I see in some cryptographic papers, that the authers of those papers utilize of a hash function such that that hash function converts an integer value or octet-string value as input, to a point on an ...
0
votes
1answer
202 views

Real-world example for Diffie–Hellman key exchange

I read in Wikipedia about the Diffie–Hellman key exchange. But i can't imagine numbers which are hard to guess. Can anybody give me a real-world example for $p$, $g$ and the two random secrets?
0
votes
0answers
59 views

Addition a point on an elliptic curve with an integer value

Suppose $Q$ is a point in an elliptic curve such that $Q=dP$ and $d$ is an integer value, and $P$ is base point of that elliptic curve. Note $Q = dP$ means that $P+\cdots+P$ for $d$ times** and since ...
12
votes
6answers
783 views

How to find the inverse of 70 (mod 27)

The question pertains to decrypting a Hill Cipher, but I am stuck on the part where I find the inverse of $70 \pmod{ 27}$. Does the problem lie in $70$ being larger than $27$? I've tried Gauss's ...
0
votes
1answer
266 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 ...
1
vote
1answer
83 views

Diffie-Hellman key exchange for three user.

Assume that there are three users that have their own secret key $d_i$ and corresponding public key $Q_i = d_i G$ such that $Q_i$ is a point in an elliptic curve. Now I'm looking for a solution to ...
1
vote
1answer
72 views

How to determine which encryption system is being used?

I came across this question in a local contest. I was not able to solve it at that time. Also, no solution was provided. I was wondering if someone can help me to understand how to tackle this kind ...
0
votes
1answer
72 views

Cryptography finding $\bar{k}$

In order to transmit messages in a secure way, some sort of scrambling or encoding of the message is necessary. Without doing so, sensitive information about intended troop movements or information ...
4
votes
1answer
93 views

Solving $x^y + y^x = a$

If $a$ is given how can I calculate $x^y$ and $y^x$ the fastest way? Is there any other way than brute forcing? How is this type of equation called? Let's say $x$ and $y$ must be $>1$ and non ...
2
votes
1answer
90 views

Cyber paper and pencil

Imagine that you would like to write down your passwords or other critical information into a sheet of paper. Could an algorithms without using a computer be so good as to avoid people of cracking ...
1
vote
0answers
41 views

Why the following observations regarding lattices hold?

The following is an excerpt of a recent paper on lattice cryptography: Let $n$ and $q$ be integers [...], and let $\beta > 0$ . Given a uniformly random matrix $A \in \mathbb Z^{n \times m}_q$ ...
0
votes
1answer
77 views

Cyclic Groups: Modulo operations in exponents possible?

I'm trying to follow CCat's Zero Knowledge Proof example, which was quite similar to the $\Sigma$-protocol example in my books. And whith both of them I'm struggeling. When I try to test CCats ...
3
votes
1answer
312 views

Adding points of an elliptic curve over a finite field

I'm a bit confused with how fractions are handled with adding points of elliptic curves over finite fields. Below is an example from the text which I am trying to understand: The part that ...
0
votes
1answer
337 views

Extension of Fermat's little theorem with Carmichael numbers

I'm a bit confused about the nature of one of my homework problems. It is requesting an explanation for why a congruence holds for $a^n \equiv a \;(\!\!\!\mod n)$ for a composite $n$, however this ...
1
vote
3answers
95 views

How would you reverse this double-variable equation?

So I have an example function: $$f(a,b) = \frac 12 ((a+b)^2 + 3a + b)$$ It "encodes" two variables into one unique number. Assuming a and b are always positive, how would you write a function to ...
2
votes
1answer
111 views

Problem related to Chinese Remainder Theorem

I'm not sure if there is a typo in the question or if I am incorrect (will point out as I get to it), but I am given that $a,b,m,n$ are integers with $\gcd(m,n) = 1$ and that \begin{equation} c \equiv ...
3
votes
2answers
122 views

Is $2+5x$ a primitive root in $\mathbb{F}_7[x]/(x^2+1)$?

The question I'm inquiring about is all in the title, but I would be more interested in a few things related to the question which I don't know. I know what a primitive root of $\mathbb{F}_p$ is for ...
1
vote
1answer
54 views

Is it possible for a singular matrix to be invariant on this interval?

I'm creating a code that that uses a matrix or matrices as a key. For example, given each string of $n$ letters, construct it into a vector using its position in the alphabet, and multiply it by an ...
0
votes
1answer
60 views

Interpolating a linear transformation

I'm experimenting with some rudimentary ideas for data encryption (I've never formally taken a cryptology class). An idea that I had for an encryption was to use matrices. So I treat a data set as ...
1
vote
0answers
38 views

Discrete Logarithm Problem in $\mathbb{F}_{p}$ and using Elliptic curves

I want to learn about the hardness of the DLP in $\mathbb{F}_{p}$ and using Elliptic curves, and the best attacks against each. I want to be able to compare the hardness of the problem in the two ...
2
votes
1answer
55 views

How to compute $x$ and $y$

How can one find in an efficient way $x,y \in \mathbb{Z}$ with max$\{|x|,|y|\} > 0$ as small as possible such that $\mid \pi x + e y \mid < 10^{-4}$ ? I have reduced the following lattice ...
2
votes
1answer
547 views

How to compute the modular multiplicative inverse on WolframAlpha?

$e = 17$ $\varphi(3233) = (61 - 1)(53 - 1) = 3120$ Compute d, the modular multiplicative inverse of e (mod φ(n)) yielding d = 2753. ...
2
votes
0answers
76 views

has any cycle found in MD5?

We are not sure whether MD5 has fixed point or not. But since the sample space is finite, it must have cycles: $$ A →(MD5)→ B →(MD5)→ C →(MD5)→ D →(MD5)→ A $$ Has any research been done on MD5 to ...
1
vote
1answer
1k views

multiplication in GF(256) (AES algorithm)

I'm trying to understand the AES algorithm in order to implement this (on my own) in Java code. In the algorithm all byte values will be presented as the concatenation of its individual bit values (0 ...
3
votes
0answers
65 views

Does there exist an operation like bitwise-xor over non-power-of-2 domains?

I want a function for enciphering a single letter that takes two letters as input, produces one letter as output, and has the same properties as bitwise XOR. The problem is that the range of inputs ...
0
votes
0answers
81 views

Is Hash(bG) equal to b(Hash(G))?

Assume b is an integer, G is a basepoint in an elliptic curve, and Hash is a one-way hash function. Is Hash(bG) equal to b(Hash(G)) ? or not? Note: A hash function is any algorithm or subroutine ...
3
votes
1answer
107 views

Is the number of quadratic nonresidues modulo $p^2$, greater than the number of quadratic residues modulo $p^2$?

Let $p$ be a prime. The number of quadratic nonresidues modulo $p^2$, is greater than the number of quadratic residues modulo $p^2$. Is that statement true or false? Why? Thank you.
0
votes
2answers
49 views

Determine amount of congruent numbers

I found the claim in a paper that there are at max 8 integers mod $2^{130}-5$ congruent to one integer mod $2^{128}$. $$u \pmod {2^{130}-5} \equiv g \pmod {2^{128}} \quad\text{ with }u \in U \quad ...
0
votes
0answers
51 views

Formula for checking the probability of a character appearing multiple times consecutively in an encrypted string

I am a young CS student with a specific interest in Cryptography, but I am relatively new to the field. Yesterday I came across a question I could not answer by myself, so I thought I'd ask some more ...
0
votes
0answers
74 views

How to calculate RSA Cryptography for small prime numbers?

Probably duplicate of Why are very large prime numbers important in cryptography? But my question is,what if we start with two small prime numbers say $p = 3$, $q = 5$ and $n = pq = 15$, $\phi(n) = ...
7
votes
1answer
154 views

Are there practical applications to the new prime pair proof?

I've recently heard that its been proven that the set of prime pairs that are separated by no more than 70,000,000 is infinite. Does this have any impact on cryptography or another practical ...
0
votes
3answers
178 views

Mathematics for cryptography.

Besides number theory, what other areas should I study for crypto. I did my undergrad in Comp Sci so the crypto course didnt have much mathematical topics. But for a grad specilisation in crypto I ...
1
vote
1answer
62 views

RSA encryption theory - modulo theory

I'm a bit mathematically challenged and have been working on the RSA cipher (good start). I can find the public and private keys and know how to work do modulo operations on a calculator. The problem ...
0
votes
1answer
92 views

RSA cryptosystem: If $k$ is a multiple of $\phi(N)$, then $k=2^t r$ with $r$ odd and $t\geq1$

I'm reading Twenty Years of Attacks on the RSA Cryptosystem by Dan Boneh and trying to understand the proof of the Fact 1 on page 3. Fact 1: Let $(N,e)$ be an RSA public key. Given the private ...
0
votes
1answer
103 views

If sent the same message m to Alice and Bob, how someone who follow the channel can find m ?

Alice has public key (n,ea) and Bob has public key (n,eb) with gcd(ea,eb)=1. If sent the same message m to Alice and Bob, how someone who follow the channel can find m ?
-2
votes
2answers
281 views

RSA: Prove that all messages encrypt to itself [closed]

RSA: Prove that all messages encrypt to itself if $p=5$, $q=17$, $e=33$.
0
votes
1answer
200 views

RSA: What message will Alice receive?

In RSA, Alice chooses $p=47$, $q=57$, public key ($n=2679$, $e=11$). When Bob sends the message $m=3$, what is the message that Alice will read?
1
vote
3answers
60 views

Consider $x^4 \pmod {pq}$, with $p = q = 3 \pmod4$.

Consider $x^4 \pmod {pq}$, with $p = q = 3 \pmod 4$. Would someone explain to me why exactly one of the four square roots of $x^4 \pmod {pq}$ is also a square? This result was given without proof ...
2
votes
0answers
205 views

Extending the Diffie-Hellman protocol to multiple parties

I'm going through a Coursera cryptography class, and there appeared an interesting (and currently open) problem about extension of Diffie-Hellman protocol to multiple parties, while preserving the ...
1
vote
0answers
48 views

Questions regarding the use of Index Calculus for finite fields and elliptic curves

Ok I have a few questions that hopefully some people can answer: For the Index Calculus applied to the Discrete Log Problem in $\mathbb{Z}_p^*$. I first thought that if we could find the ...
1
vote
1answer
175 views

Does “short integer solution” lattice problem admit hard instances with q=2?

Let $q$ be a prime, $m,n$ be integers with $m>n$, and $\beta$ be a real number. Moreover, let $A$ be a matrix in $\mathbb Z^{n \times m}_q$. In the "short integer solution" (SIS) lattice problem, ...