Questions tagged [cryptography]

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

Filter by
Sorted by
Tagged with
0
votes
0answers
43 views

What a hash function is [closed]

What does a hash function represent? How do we define it mathematically and why is it so important? What are the properties of a hash function? (for example is it injective etc.) I would appreciate ...
0
votes
0answers
25 views

Secret sharing scheme of a polynomial function of degree $t$ and how $s$ is calculated after the reconstruction?

Suppose that we want to share a secret $s\in S$ in $t$ parts and we use a secret sharing scheme to do it. Suppose that $|Y|\geq |S|$ is a field sufficiently large with cardinality $p$ and a polynomial ...
0
votes
0answers
47 views

Explain RSA in a math language that I can understand

Having not a super high-level background in math, I can't understand several parts of RSA. I know that you select a number n, and two numbers e and d. Then you have ed= mod(φ(n)), which looking it up ...
-3
votes
0answers
45 views

Secret sharing schemes without cryptograpy? [closed]

Are there any details about secret sharing schemes where without cryptographic tools using only some tools of linear algebra and group theory?
1
vote
0answers
103 views

If we re-define this function could it be bijective?

According to this paper in page $4$ where it describes the encryption scheme where a cipher function is defined as it follows $$\rho:T\times Y \to X$$ such that $|Y|\geq |T|$, where $y\in Y$ is the ...
0
votes
0answers
12 views

Proving modular equivalence of sum with noises [closed]

I'm trying to prove the following let $x \xleftarrow{$} \mathbb{Z}_{R'}$ be uniformly sampled from $\mathbb{Z}_{R'}$. Let $R = N(R' - 1) + 1$. Now let $ y \xleftarrow{$} \mathbb{Z}_R$. Now let there ...
0
votes
1answer
53 views

How did we discover that this quadratic residue oriented PRNG generates unique numbers in a sequence?

Question (tl;dr) How do we know that even for extremely large numbers like even far past $32^{15}$ (any bigint, or any number really), that as you increment the sequence from $0$ to $n$, $n$ being the ...
0
votes
0answers
34 views

Could someone tell me how such a secret sharing scheme could work?

Taking into account a post here which is the following, I want to make some questions. A secret sharing scheme is a method of distributing finite pieces of information (called shares $\alpha_i$) among ...
2
votes
0answers
73 views

Intuition behind entropy requirements in information theoretic structures

Let $X$ be a random variable that takes values in a finite set $\mathcal{X}$. For any $x\in\mathcal{X}$, let $p(x) = P[X = x]$ be the probability that $X$ takes the value $x$. The entropy of $X$ is ...
1
vote
1answer
48 views

What is the formula for determining how many errors a generator matrix can correct?

I am wondering whether or not there is a generic formula for determining how many errors a generator matrix is able to correct if also provided the field the code is in. For example, given the ...
0
votes
0answers
38 views

Determine if a generator matrix G' also generates the same code C (generated by generator matrix G)

I am asked that if I know that a binary code $C$ is generated by a matrix $G$, how to show that another matrix $G'$ does or does not generate that same code $C$. I have deduced the parity matrix $P$ ...
0
votes
2answers
51 views

Why is the complexity of N=pq for RSA considered as exponential time?

I'm studying about RSA algorithm for 16-bits and noticed that the complexity of N=pq is considered as exponential time. In the algorithm, p and q are two random and distinct strong primes. All the ...
1
vote
0answers
54 views

Cryptography books?

Not sure if this is the correct place to post. If not, maybe someone knows where I should go :) I am curious about cryptography and have taken some related courses through my studies. However I was ...
3
votes
1answer
62 views

Stochastic independence and linear combination of uniform random variables

The following theorems are part of this paper Suppose that $(X_1,\dots,X_k)$ is a family of i.i.d. uniform random variables in $\mathbb{F}^{n}$ (why do we assume that the exponent of the field/set/...
0
votes
1answer
57 views

Encrypting plaintext into ciphertext using RSA.

Good Day, I am attempting to curate ciphertext using RSA encryption given values for the message to encrypt using the encryption algorithm: $c = m^e Mod N$ I understand the elements that go into ...
1
vote
1answer
43 views

Inverse with Extended Euclidean Algorithm

I'm solving a task from https://www.coursera.org/learn/crypto/, particularly the following question: I know that 3x - 5 = 0 and since "ax + b = 0" that implies "x = -b * a^-1", ...
0
votes
1answer
36 views

Infinite Sequence vs. Indexed Set

I'm having a look at this provable cryptography tutorial and early on there is a definition of something called a "probability ensemble" which I haven't come across before. A probability ...
-1
votes
0answers
19 views

Extracting product of sum

I am currently facing a cryptographical challenge and need to transform this equation. $$N = (x * a +b) * (x *c+d)$$ I need the isolated product $$b*d$$ without any relation, so e.g. $$b*d = N - x*a*x*...
1
vote
0answers
38 views

Designing $3$-bit input/output function

I want to find a function(S-box) (if it exists) such that $S(x) \not = x$ for every input $x$ and also changing each single bit causes at least two bit changes. This means that if we take $S(000) = ...
0
votes
0answers
44 views

Prime and co-prime numbers importance in Cryptography

I am currently writing a math paper for school regarding RSA encryption my focus lies on the importance of prime and co-prime numbers within the algorithm. I understand that this is a "trap-door&...
1
vote
0answers
40 views

Notation in number theory used in cryptography and game theory

We have the following notation, that is $$x_i=z_i-y_i\pmod{n_i}$$ where $z_i$ is a random variable with support $\{0,1,\dots,n_i\}$, $y_i$ is uniformly distributed random over $\{0,1,\dots,n_i\}$ and ...
0
votes
0answers
19 views

Is it possible to construct a hash function that accepts multiple keys and returns the same value if at least one key is the same?

How to construct a hash function that accepts multiple keys as input and returns the same value if at least one input key is the same, no matter which keys are identical? For example, the desired hash ...
0
votes
0answers
39 views

Solve RSA problems with e=2 and n is product of three primes

Summarize problem: Given: n=p*q*r with p,q,r are primes number and $p\equiv3(\text{ mod }4)$,$q\equiv3(\text{ mod }4)$,$r\...
0
votes
0answers
22 views

Turing complete Language that produces proofs for its results

Would it be possible to create a Turing complete programming language, where the result of a program always includes a easy to verify proof that the result is valid. Let me explain in more details. ...
-1
votes
1answer
63 views

Inversion of partial hash information on SHA-256 [closed]

Can the original data be recovered from the known first 32 bytes of an SHA-256 hash value? The first 32-byte of the hash value given as; $\texttt{0x141fb569eaa5fe6f71eb18029e652fef}$ HINT: The data ...
2
votes
1answer
36 views

Principle of Inclusion-Exclusion with Substitution Ciphers

Consider an alphabet with $2n$ symbols and the substitution cipher that maps $p_i$ to $c_i$ for all $i$. If the numerical representation of $p_i = i$ for every $i$, how many substitution ciphers exist ...
0
votes
0answers
50 views

Using value outside galois field and do calculations inside

currently, I'm working Shamir Secret Sharing algorithm and for not so big numbers (long passwords more than 7 chars) my calculations are broken because of overflows. The case is this: I have a big ...
0
votes
1answer
38 views

Confusion about Modulus Multiplication and Exponents

I have two questions about the modulus function. In my book (Computer Security (2nd Edition), Chapter 10, Page 314), it says that: 1847(1002, 493) mod 2503 = (460, 2083). Note that (x, y) mod p = (x ...
1
vote
1answer
60 views

Why can this cryptosystem be easily broken?

I am having trouble understanding the concept of public-key cryptography and why some cryptosystems can be easily broken when used in a certain way. Here is an example. Suppose we have a communication ...
0
votes
0answers
50 views

Why is $\mathbb{Z}_{100}$ bad for cryptography and how can it exploited.

I read that fields like $\mathbb{Z}_{p}$ given $p$ is prime ensures that the key is "equally distributed". This makes it hard to reverse engineer and find any exploitable properties. I want ...
0
votes
0answers
42 views

Password alternatives in the cryptography

All the modern informational systems are based on a password concept. The password idea is the cornerstone of contemporary cryptography as well. Assume that quantum computers can and will succeed in ...
0
votes
1answer
47 views

is the intersection with a Lattice still a Lattice?

Given a lattice A in $R^n$, and a subspace B of $R^n$. is the intersection $A \cap B$ a lattice? Thanks
0
votes
0answers
27 views

Time Complexity Baby Steps Giant Steps

This has been driving me mad. On wikipedia's page on baby steps giant steps it gives the time complexity of the algorithm as $O(\sqrt n)$. It even gives looking up a value in a hash table as how you ...
1
vote
0answers
26 views

Exploration of specific groups (𝕌21,⊗21).

Consider the Group (𝕌21,⊗21). a) Determine the order of this Group. b) List the complete set of elements of this Group. c) Construct the Cayley table of the Group. d) Determine if two distinct ...
0
votes
1answer
25 views

Need help understanding the proof of correctness of deciphering algorithm in the original RSA paper. [duplicate]

In the paper "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems" by R.L. Rivest, A. Shamir, and L. Adleman, they prove correctness of deciphering algorithm by following ...
0
votes
0answers
16 views

Secure multiparty computation and dynamic programming solution concept?

Consider the usual problem of secure communication, where each of the $I$ agents have a private signal $s_1,s_2,\dots,I$ and they wish to compute any function $f(s_1,s_1,...,s_I)=(x_1,x_2,...,x_I)$ in ...
2
votes
1answer
130 views

RSA decryption with some additional condition

I’m to find the message in RSA with an additional condition. Suppose $M$ is the message and $n$ is the large prime used here. What I know is $n,e,c$ where $c \equiv M^e \pmod n$. If I know that there ...
1
vote
0answers
39 views

Secure multiparty computation when players observe Gaussian Random variables

I am searching to find information about the topic of Private Secure Multi-Party Computation, which alse seems to be of major significance in machine learning these days. I am starting with some ...
0
votes
0answers
30 views

Probability of Cracking Private Key Given N Attempts

Suppose there are a total of $r=6.6*10^7$ Ethereum addresses with a non-zero balance and my goal is to find the private key to at least one of them. There are $a=2^{160}$ total possible public ...
2
votes
0answers
98 views

Understanding a proof by Gossner (1998) - see sections $5$, $6$ and $7$.

The following definitions are taken from the paper of Gossner (2000). I want to understand how he proves the theorem that is the main result in his work. I give four definitions and the theorem which ...
0
votes
0answers
22 views

Permutations, random variables and cryptography

Can anybody provide sources to read and learn about how to model a communication device using permuatations and probability theory? For example, take the sender receiver problem, whre we have two ...
1
vote
1answer
21 views

Cryptography, Starkware, Number Theory: Special case where the powers of g form a subgroup

Starkware cryptography uses a simplification result that I don't fully understand and I was hoping someone could help explain it to me. https://medium.com/starkware/arithmetization-ii-403c3b3f4355 ...
1
vote
1answer
58 views

Finding (e,d) in RSA - mathematical problem

I've been trying to solve that but it seems to me illogical. $p$ and $q$ are large prime numbers and $n=p*q$. Alice wants to send Bob message $M$ using RSA. Alice lets Eve choose the keys for her ...
0
votes
0answers
50 views

proving no primitive roots exist modulo $2^n$ for n $\geq$ 3

Ive been asked to prove by induction that no primitive roots exist modulo $2^n$ for n $\geq$ 3. I have proven true for base case $n=3$, and assumed to be true for $n$. I'm now stuck at this point: $${...
0
votes
0answers
18 views

What is the probability of an attacker winning the following cyber attack scenario?

An attacker with a high hash rate is playing against a network in a proof of work situation. 10% of hashes open up a vulnerability for the attacker, his goal is to find such hashes and broadcast it ...
0
votes
0answers
27 views

Crytpographic theory books?

I was reading a paper in communication mechanisms, and the tools that are used from the authors have been taken from cryptograpgy. If anyone have some time to check the paper nd see the proof of ...
3
votes
1answer
92 views

Location-privacy-preserving protocol for finding relative direction?

Sorry if this is a silly question, but: imagine there are two agents on a finite 2d plane. Each agent knows her location but not the other's, and they want to find the relative directions between them ...
2
votes
1answer
49 views

Is factoring primes $pq$ eqivalent to discovering $p+q$, thus binding $q$ and the search for $(p+q)$ when $(q/p) < 4$?

Background Some crypto algorithms rely principally on the difficulty of factoring two prime numbers $p$ and $q$. For the purpose of this discussion, assume $p<q$. (The top of this article is ...
1
vote
2answers
118 views

RSA Fast exponentiation

I am reading a book on cryptography - A mathematical introduction to cryptography (Hoffstein et. al, 1st Edition) and through chapter 3.2, I found this... which describes the RSA system. The author ...
0
votes
1answer
43 views

What system has modular inverses for non primes too?

Is there a system that has modular inverses for non prime mods? Ultimately what I am trying to do is design a hash function that given a list of n outputs (mod m) and inputs (large arbitrary integers),...

1
2 3 4 5
35