texts: How are blockchain keypair private keys hidden from miners, and how are they generated in the first place?

texts:
I don't know how blockchain keypairs are programmatically generated, and equally important - how they are able to verify their keypair using a private key to a remote server - while keeping their private key entirely private.

How are blockchain keypairs generated, and private keys kept hidden by the remote server that is able to authenticate your account with some type of signing?

Is a public key a random hash and a private key the hash that parented the public key? If not, how? And how do they stay hidden the target network?

I am using encryption references in my IDE but am unsure how to utilize them effectively with a blockchain network.

Private Declare Sub MD5Init Lib "cryptdll" (Context As MD5_CTX)
Private Declare Sub MD5Update Lib "cryptdll" (Context As MD5_CTX, ByVal strInput As String, ByVal lLen As Long)
Private Declare Sub MD5Final Lib "cryptdll" (Context As MD5_CTX)

Private Function CalcMD5(sEncryptString As String) As String
    Dim strBuffer As String
    Dim myContext As MD5_CTX
    Dim result As String
    Dim lp As Long
    Dim MD5 As String

    strBuffer = sEncryptString

    MD5Init myContext
    MD5Update myContext, strBuffer, Len(strBuffer)
    MD5Final myContext

    result = StrConv(myContext.digest, vbUnicode)

    For lp = 1 To Len(result)
        CalcMD5 = CalcMD5 & Right("00" & Hex(Asc(Mid(result, lp, 1))), 2)
    Next

End Function

Yes, that's VB Classic. I am old, cut me a break.

I expected to understand keypairs, but I actually had no idea how they worked this entire time.


texts: Breaking keyed hash function with half-randomized input

texts:
Let's say we have keyed hash function which transforms $256$-bit input into $256$-bit output and the attacker knows the key (let's say the key is $256$-bit long). Now let's consider we will construct an input block as:

$128$-bit message (first bits),
$128$ random bits (last $128$ bits).

Now output could be kind of randomized. I think there is no way to find the $128$-bit message. Am I right? Is the message safe in this case?


texts: Are pseudorandom permutation really permutation in mathematical sense?

texts:
In security, and specifically Block Cipher (AES, DES, etc), when we talk about pseudo random permutations, is the term "permutation" refer to the same meaning as in discrete mathematics. That is, the random shuffling of elements?

So let's the input of DES has n 1s and m 0s, is the output gonna be n 1s and m 0s as well?


texts: Signature based on public key cryptography and forgery

texts:
In the definition of existential unforgeability, there is no detail about the following questions.
In general, can we suppose that a signer is also a possible adversary? When generating a signature, can we suppose that the signer behaves well?
More precisely, suppose that a signer can generate a signature that is valid for another document of his choice. Despite this, for a correctly generated signature, suppose that the signature scheme used is secure when considering an adversary who is not the signer; that is to say, this adversary cannot generate a signature for any other document. Is this signature scheme considered secure?
What is the standard (conventional) hypothesis about that?
I update in reaction to the comment:
In fact,

If the signer behaves well, then the signature is unforgeable (for the signer or any adversary who is not the signer).

If the signer misbehaves, then the signature is forgeable (for the signer, without using the key, and for any adversary).

Is this kind of scheme considered secure in the sense of existential forgeability? Can we suppose that the signer behaves well?


texts: Hash function for sets with efficient membership testing

texts:
Is it possible to construct a collision-resistant function that hashes a set of values but also allows membership testing?

Essentially, I'm looking for a pair of functions, $\text{H} : \{0,1\}^{**} \rightarrow \{0,1\}^*$ and $\text{M} : \{0,1\}^* \times \{0,1\}^* \rightarrow \{0,1\}$, where $\text{H}$ hashes a set of bitstrings into a single bitstring, and $\text{M}$ checks if a given bitstring was in the set of bitstrings that were hashed.

The security requirement: It must be impossible for any (appropriately bounded) adversary to find a set $x_1,...,x_n$ and value $y$ such that $\text{M}(y,\text{H}(x_1,...,x_n)) \neq y \in \{x_1,...,x_n\}$. I believe this requirement also implies that $\text{H}$ is collision resistant.

A simple solution is to define $\text{H}(x_1,...,x_n) = f(x_1) \| ... \| f(x_n)$ where $f$ is a normal collision-resistant hash function (e.g. SHA-2), and let $\text{M}(x,h)$ return $1$ if $f(x)$ is found in $h$. In this scheme, the output of $\text{H}$ grows linearly with the size of the set.

Is it possible to build a more efficient construction?


texts: Signal protocol: when, and why, is X3DH run again between the same two users?

texts:
This question concerns the Signal protocol's X3DH key agreement protocol as documented here.

Obviously, if Alice and Bob have never contacted each other before, they need to run X3DH at least once to agree on a key.

However, it is unclear to me why X3DH needs to be run more than once between the same two users: now that they have agreed on a key, and given the Double Ratchet algorithm is used to generate new keys for each message to ensure perfect forward secrecy, why would they ever need to run X3DH again?

Without the need to run a key agreement protocol a second time between the same two users, a simple DH between Alice and Bob's identity keys should suffice, and perfect forward secrecy is not an issue since the protocol would never be run again. Only if the protocol needs to be run more than once would X3DH be called for, to restore perfect forward secrecy.

I imagine this is due to an implementation decision of not committing any keys beyond the bare minimum (private keys for the identity key, signed prekey and one-time prekeys) to non-volatile storage, so that when the app is restarted, the protocol would need to be run again. Can anyone confirm?


texts: Secure asymmetric encryption with 32byte ciphertext

texts: I need securely asymmetrically encrypt the up to 16 bytes plaintext and receive up to 32 bytes ciphertext. I found that ElGamal produces ciphertext that is 2 times keysize. So I would need to use 128bits keysize, which are not secure enough. I can use any keysize, but the ciphertext must not exceed 32bytes. Is it possible with other schemes?


texts: Why do different applications of hash functions demand different properties of the hash function?

texts: A strong cryptographic hash function in general must guarantee several properties, including: Preimage resistance, second preimage resistance and collision resistance. It turns out, however, that certain applications only require a subset of the properties while others require all of them. The table below gives a summary of which applications require which properties (from Stalling's book). Can someone give an explanation for the properties required by each application? For example, it makes sense that one-way passwords require preimage resistance since we don't want a person to compute the password from the hash. But I would not understand why one-way passwords do not require collision resistance (i.e., if two different passwords give the same hash, then an impostor could more easily break in). Anyone with an explanation for the different properties? The table is from an authoritative textbook in the area (Stalling's book).


texts:
Bob is holding a secret-bid auction using ElGamal encryption. He chooses a “safe” prime $p$ of sufficient size, a generator $g$ in $\operatorname{QR}(\mathbb Z_p)$ and a value $b$ in $[1, p]$. He then calculates the value $B = g^b\bmod p$, and publishes the values $g$ and $B$.
Alice wants to place a bid with value $m$. She chooses a random value $k$ in $[1, p]$, and computes two values: $r = g^k \bmod p$, and $t = m\cdot B^k \bmod p$. The values Alice sends are $r$ and $t$.
Bob can recover Alice’s bid by calculating $m' = t \cdot r^{-b} \bmod p$.
Mallory intercepts Alice’s message, and can replace it with her own. She wants to inflate Alice’s bid by 10x to make sure Alice pays a much higher price than necessary. What value does Mallory change Alice’s bid to? Let the new values be $r'$ and $t'$.
How do you approach this problem?


texts: Calculating RSA Public Modulus from Private Exponent and Public Exponent

texts: If I know the private and public exponents ($d$ and $e$) of an RSA key pair, is it possible to (efficiently) calculate the public modulus $n$?


texts: Why does decryption in RSA not fail with 2 different moduli?

texts:
In RSA, we choose $p,q$ and calculate $\phi(n)=(p-1)(q-1)$. We then choose a public key $e$, and calculate its inverse modulo $\phi(n)$: $d\cdot e=1 \mod(\phi(n))$.

But then, when we decrypt a ciphertext $y=x^e \mod(n)$, we use the different modulus $n$ rather than $\phi(n)$: $x=y^d \mod(n)$. This is equal to $x^{e\cdot d \mod(n)}$, which supposedly equals $x^1$. But I don’t understand this last step, because we chose $d$ such that $e\cdot d=1 \mod (\phi(n))$, not such that $e\cdot d=1 \mod(n)$


texts:
Is it possible to find the key of an HMAC-SHA-512 given the input and the hash output?

If so, what algorithm if any prevents this?

I'm working on a simple E2E communication system between two self-managed servers, and my idea is to store a static key on both servers, and it is critical that the stored key cannot be reverse-engineered from the sent requests. The requests would contain both an unencrypted and encrypted version of a string, the encrypted one being hashed with the stored key. This does sound unorthodox, but the maths checks out if the mentioned reverse-engineering operation is impossible.

EDIT: Clients will not be able to use an old authentication string to authenticate a new message.


texts: What is the simplest digital signature algorithm known?

texts:
The hardest part about this question is explaining what I mean by simple. I'm measuring simplicity as, simply, the amount of lines of code it takes to implement that algorithm in a simple programming language - say, the untyped lambda calculus, Scheme, vanilla ES5 JavaScript. Of course, this is not possible to measure directly, but some things are just obvious. For example, any algorithm depending on any kind of algebra (multiplication, exponentiation, division, modulus, whatever) is not simple because implementing Bignum takes an obscene ton of lines itself!

For example, this wikipedia article claims the Schnorr signature is the simplest known scheme, polluting the Google results with such a blatantly wrong claim, because this proposal can clearly be implemented with much less code in absolutely any language without native big-integers.

That is why ECDSA, DSA, RSA aren't simple, they depend on way too many number-theoretic functions. I'm looking for a signature scheme that emerges from some kind of natural process, for example, L-systems, cellular automatas. Those are truly simple to implement in any kind of language, no dependencies!

So, what is the simplest digital signature algorithm known?


texts: Construction of secure Elliptic Curve subgroup over a much larger field

texts:
How can we construct an Elliptic Curve subgroup of cryptographic interest out of an Elliptic Curve over a much larger finite field, including the familiar $\Bbb F_p$ for prime $p$? The Discrete Logarithm Problem and related should conjecturally require $\mathcal O(\sqrt q)$ field operations, where $q$ is the subgroup's order, which must be known.

Motivation: in a signature à la Schnorr, having an analog to Schnorr (sub)groups, but with resistance to NFS and index calculus regardless of choice of $p$; yet still with  parameter $p$ to slightly tune up the cost of field operations, for likely increased security against ASICs and hypothetical quantum computers usable for cryptanalysis, at a given group/signature size.

One way to fulfill that need would be a randomized generation procedure parametrized by bit sizes for $p$ and $q$ (much larger for $p$), yielding primes $p$ and $q$ and the equation of an Elliptic Curve group over field $\Bbb F_p$ having order a multiple of $q$, with some presumption of hardness of the DLP.

I care much more for security for a given size of $q$, and simplicity of implementation on the signature verifier side (where side channels are a non-issue), than on speed, and on ease of making a secure (side-channel resistant) implementation on the side with the private key.

I envision a 192 to 512-bit $q$ for 96 to 256-bit conjectured security (counted in field operations in $\Bbb F_p$), and $p$ several times that size (at least twice).


texts: How to create and send a symmetric key using GPG

texts:
I want to communicate with a friend (he lives in another country so we can't exchange fingerprints or keys physically, I could post him a USB disk but I'm sure I can do it through the web).

I'm pretty familiar with public key cryptography but this is the first time I've decided to use a symmetric approach. There are a few things I'm wondering:

Do I need to generate a special type of key for this, or can I just generate a 4096 bit RSA key pair with gpg --full-gen-key like I usually would?
Does it make a difference whether I use my private key or public key? Is there any real difference between these two keys. meaning if I encrypted a file using my private key would it be the same quality as if I had used the public key?
So in addition to the password for the message I sent him, my friend needs a copy of the key I use to decrypt it so we then have a shared key. Would it be a good idea to send both keys (the private and public) so when a third party encrypts something with our public key, we can both decrypt it. Have I got the right idea there, or would that introduce any security risks to this symmetric communication system?

This is just a practice exercise, we're both interested in cryptography and want to make our online communications 100% encrypted and secure, in order to develop a practical understanding of cryptography, steganography and security. This is step 1, we will send exchange email addresses and secure IM service account details. And from there we can discuss how to step things up and gradually reach our goal of being 100% encrypted and secure. I would greatly appreciate any tips, insights, methods, pointing out flaws in my methods and things I haven't thought about yet.

One challenge which is a fun one is getting the key to him. I'm not gonna complicate it too heavily, but heres what I'm thinking:

Compressing the key pair into a password protected zip archive, and embedding it into a PDF file or PNG, or whatever file type won't seem weird with the extra size.

A more secure way would be to post a USB key to him of course, but we wanna do this entirely via the web for now.


texts: Distribution based integer factorization

texts:
The past week I've been looking into - and playing with - algorithms for factoring RSA moduli.

From what I understand, it's important that the primes p and q are of the same magnitude as the square root of N, but they shouldn’t be too close. To find out how close p and q are to sqrt(N) in the real world, I've used OpenSSL to generate a bunch of numbers.

The following image shows a graph. The x-axis shows N, the modulus. The y-axis shows how far p is from the square root of N, in percentage. This graph shows values for 5000 128-bit RSA moduli.

What I find interesting about this graph is that if a 128-bit modulus starts with "20...", I know that p can not be further than 2 percent from the square root of N.

Do algorithms exist that make use of such distributions? What would be the best attack if I know in what range p is located?

Update

If anyone wants to replicate the graph or check for errors in my code, here is the code used for generating OpenSSL N,p,q pairs:

from os import system
import re

def tardReplace(reg,data):
    n = reg.findall(data)[0]
    n = n.replace("\n","").replace("\r","").replace(":","").replace(" ","").replace("\t","")
    return int(n,16)

modDict = {}
genBits = 128
genAmount = 5000

fileName = "generated/" + str(genBits) + "bitRSA" + str(genAmount)
outf = open(fileName + ".txt", "w")

for i in range(genAmount):
    system("openssl genrsa -out foo.key " + str(genBits) + "; openssl rsa -text -in foo.key > values.txt")
    with open('values.txt','r') as f:
        data = f.read()

    if genBits <= 64:
        modReg = re.compile("modulus: ([0-9]+) ")
        mod = modReg.findall(data)[0]
    else:
        modReg = re.compile("modulus:([ \n\r\t0-9a-f:]+)publicExponent")
        mod = tardReplace(modReg, data)

    if genBits <= 128:
        prime1Reg = re.compile("prime1: ([0-9]+) ")
        prime1 = prime1Reg.findall(data)[0]
        prime2Reg = re.compile("prime2: ([0-9]+) ")
        prime2 = prime2Reg.findall(data)[0]
    else:
        prime1Reg = re.compile("prime1:([ \n\r\t0-9a-f:]+)prime2")
        prime1 = tardReplace(prime1Reg, data)

        prime2Reg = re.compile("prime2:([ \n\r\t0-9a-f:]+)exponent1")
        prime2 = tardReplace(prime2Reg, data)

    outf.write(str(mod) + "," + str(prime1) + "," + str(prime2) + "\n")

outf.close()

system("sort " + fileName + ".txt > " + fileName + ".sorted.txt")

And here is the code for making the graph:

import matplotlib.pyplot as plt

with open('../../rsaGen/generated/128bitRSA5000.sorted.txt','r') as f:
    data = f.read().split('\n')

x = []; y = []

for line in data:
    if line == '':  continue
    n,p,q = line.split(',')
    n = int(n);     p = int(p);     q = int(q)
    p = min(p,q)

    sqrtn = n ** 0.5
    diff = sqrtn - p
    percent = (diff/sqrtn)*100

    x.append(n)
    y.append(percent)

plt.scatter(x, y)
plt.show()


texts: CCA2-secure encryption based on LWE/Ring-LWE

texts:
As I understand it, cryptosystems based on LWE/Ring-LWE are typically only IND-CPA, and fail to satisfy IND-CCA2.  In fact, it appears that chosen ciphertext attacks could allow secret key recovery (!).

What is the best known IND-CCA2 secure encryption algorithm based on (Ring-)LWE?  What about key exchange?


texts: How to fix the IND-CPA+ problem in CKKS?

texts:
In paper On the Security of Homomorphic Encryption on Approximate
Numbers
the author gave an attack on CKKS, then how to fix it?


texts: Does a practical collision attack on a cryptographic hash function also mean it fails “indistinguishable from random data”?

texts:
It is knowns that SHA-1 has been broken in practice using collision attacks. Related to SHA-1 this mainly had a negative impact on the security of

Digital Certificate signatures
Email PGP/GPG signatures
Software vendor signatures
Software updates
ISO checksums
Backup systems
Deduplication systems
etc.

Thinking about a LUKS related Q&A at our site, I'm wondering if a collision attack also means that the broken hash like SHA-1 can – or maybe even should - also be considered “distinguishable from random data” (from a cryptographic point of view).

Does a practical collision attack on a cryptographic hash function also mean we can (or should) consider it to fail “indistinguishable from random data”? Or does a collision attack have no influence on that?


texts:
Suppose there are 3 persons, Alice, Bob and Peter.

They are identified by their pseudonyms (public RSA keys).

Alice has a key Alice, Bob has Bob-Work and Bob-Friends. Peter has Peter.

Peter knows Alice. Alice expresses trust to Bob-Work.

Peter knows Bob-Friends.

The question is, How can Bob-Friends prove to Peter, that Bob-Work he's being trusted by Alice (and therefore Bob-Friends too), without revealing that Bob-Work and Bob-Friends belong to the same person, and/or plausibly deny such a fact?

NOTE: We do not discuss timing attacks here (such as "Please express trust to THAT pseudonym and I'll see who will appear as trusted to me afterwards")
I have a possible solution involving a "credit system", where participants emit "trust tokens" which can then be transferred by their recipients. But, this has a downside of having to support a LONG credit transfer history. Is there a solution that does not need it?

P.S. Please retag this question appropriately (reputation, trust etc) - I can't create new tags yet :)


texts:
Let $H$ be a hash function that is both hiding and puzzle friendly. Consider $G(z) = H(z) \Vert z_l$ where $z_l$ is the last bit of $z$. Show that $G$ is puzzle frielndly but not hiding.

This question is from this book, page 50). I'm stuck at proving $G$ as non-hiding.

  A hash function is hiding if: when a secret value $r$ is chosen from a
  probability distribution that has a high min-entropy, then given
  $H(r \Vert x)$ it is infeasible to find $x$.

Now for given function $G$, we have:

$G(r \Vert z) = H(r \Vert z) \Vert z_l$

I don't see how $G$ fails to be hiding. If we are given $G$'s output, we just know about one fixed bit of the input. $H(r \Vert z)$ (the part of the output excluding the last bit) still makes it infeasible to determine $z$ since $H$ is hiding. How can one bit of input prevent $G$ from hiding?


texts: Source for examples with broken cryptography

texts: I've heard again and again that many crypto systems have been broken in the past for one reason or another and that it is best to use one that has been peer reviewed, etc etc. However, I've yet to see a source (website, book) that gives information about these systems. Is there such a thing?


texts: How can bit slicing be constant time, when Mix Columns is in the cipher

texts:
I'm reading about bit-slicing techniques, and one thing about it caught my mind.

The strength with bit sliced implementations are (apart from that they are fast) that they are running in constant time. This outrules side-channel attacks based on timings.

Now, my question is:
How can ciphers such as AES run in constant time, when bitsliced? The MixColumns operations works in $GF(2^8)$, so whenever an eight bit from the matrix multiplication is $1$ before the multiplication, the result has to be reduced modulo the polynomial of the Galois Field to not overflow. To me that seems like, the running time of the cipher depends on the input then? (I can understand why SubBytes, ShiftRows and constant additions are constant time).

Is the solution for bit slicing to reduce (XOR) with the polynomial after every operation, or is there a smarter trick? It seems like a slowdown, since bit slicing is often done for speed.
(I'm not an expert on Galois Fields either, so I'm not sure if it's okay to XOR with the polynomial after each operation, as that would be like adding a value to the result everytime)

Thanks for enlightening in advance! There is not THAT much documentation on bit slicing. It seems like everyone knows that its fast and knows it exists, but very few implementations has actually tried using it.

EDIT: It does not seem like, it would be okay to reduce with the irreducable polynomial after every multiplication. If I XOR the polynomial to a result, which 9th bit is $0$ (i.e. result does not overflow), then it will overflow since the irreducable polynomial in AES is $100011011$ (in bitform).


texts: What do recent announcements about solving the DLP in $GF(2^{6120})$ mean for RSA

texts:
After just reading the post Do recent announcements about solving the DLP in $GF(2^{6120})$ apply to schemes proposed for cryptographic use?

I was a bit confused. DSA, ElGamal and others are based on the assumption that DLP is a hard problem to solve. The DLP problem can be defined in different cyclic structures, but making progress in one of this structures does not imply any progress in breaking DLP in other structures?

Also, the question
Would the ability to efficiently find Discrete Logs have any impact on the security of RSA?
contains the following:

  So, given your question "Would the ability to efficiently find Discrete Logs have any impact on the security of RSA?" the answer would be yes. Furthermore, if you can solve DLP for composite moduli, you can also solve it for prime moduli.

So, we now have a improved algorithm that can solve the DLP problem for $2^{6120}$ composite moduli? Does this mean anything for RSA 1024, 2048? DSA? Or are the DLP assumtions only valid in the cyclic structure where there are used?

And why is the exponent that large? RSA, Diffie Hellman all use exponents 1024, or 2048?.

(This question could be flagged as duplicated. But because i could not pose these questions as answer i asked a new question.)

I hope the question is clear. And as always, thanks for your help!


texts:
I've been having a hard time placing DJB's analysis of Oorschot & Wiener parallel rho collision search into context.  There is plenty of discussion about the birthday bound and quantum computers in relation to hash functions, but these speedups are much more dramatic.

How does this attack alter the runtime analysis for brute forcing hash collisions?  Is it only a linear speedup, but how big are hashes going to balloon to?


texts: What are the negative consequences for choosing 8 S-boxes for DES vs 1 S-box for AES?

texts:
DES has 8 different S-boxes, and AES has only 1.

What are the negative consequences of such choices?


texts: Is garbled circuit a post-quantum primitive?

texts:
I understood garbled circuit can hide some function $f$ jointly by multi parties.
With quantum computer, can we see the circuit inside it?


texts: How to calculate entropy of a combined key

texts:
I know how to calculate the entropy of a key that relates to its selection process. For example if the key space is $1000$, entropy of a randomly chosen key is $1000$. Suppose now you have two keys $X$ and $Y$. The finale key $Z$ is a concatenation of $X$ and $Y$. There are two ways to combine. One is to use XOR and other way is to use a Key Based Key Derivation Function (KBKDF) such as HKDF. I want to know how to calculate the entropy of $Z$ when…

$Z$ = $X$ XOR $Y$
$Z$ = HKDF($X$,$Y$)

In the XOR case should I use mutual information of $X$ and $Y$?


texts: Asyncronous Rachet tree: How user movability is handled is the Rachet tree being recreated?

texts:
As I have read the latest state of art in group key agreement is the Asyncronous Rachet Tree.

But in applications like IRC that exists high user movability (users join in ans leave the room). Is there a mechanism that updates/refreshes the key when users join or leave the chat room to the ART key agreement?

So far in the paper the only refresh is mentioned when a user changes its key.


texts: How are the primes used to generate RSA keys?

texts:
I am confused about how keys in RSA asymmetric encryption are generated and what the implications for open communications are.  Textbooks say the one-way function is merely two primes (with some critical constraints) -- so how do the two primes generated get turned into keys?

Does this mean that having a public key is simply having one of the primes in a translated or equivalent form?  For example, if I were to encrypt a message with someone else's public key and the one-way function could be broken by a third party, then could they decrypt the message with a key generated by the other prime?  Does the other prime have to go through some special process to become a key?

To go further, if the encrypted message was posted in a public forum or sniffed off of a wireless network, etc. (and again, the one-way function was broken by a mysterious third party), does that mean the message could be decrypted by the third party?  Would it matter which prime was used?  What i am wondering is what is the process whereby the primes behind the one-way function are converted into keys and is that process the same regardless of encryption used?


texts:
Just started learning about Cryptography and Network Security in general, and I can't seem to grasp the understanding of the following question. Please correct me if I am misunderstanding anything.

Imagine that there exists a Pseudorandom Generator that simply doubles all key length, G(n) = {0,1}^n -> {0,1}^2n. If I have a key k and send it over to G, I now have an encrypted G(k) = k', and k' is twice the length of k. If I have a message m, encrypt it with k' with m XOR k', is it CPA secure or not?

I understand that with a CPA attack, the attacker can send any plaintext into the encryption mechanism and receive a ciphertext out of it.

My confusion is that, in the case above, what exactly is the attacking sending the plaintext into? Is it the Pseudorandom generator? Does the attacker know what type of pseudorandom generator it is? But since the attacker doesn't even have the original cipher-text or the original key, what use is it for the attacker to keep on sending his own plain-texts and get back his own cipher-texts?

Sorry if this is very confusing, but I really want to understand this before moving onto more advance topics.


texts: What is the difference between "asymmetric key cryptosystem" "asymmetric cryptography" terminology?

texts: What is the difference between "asymmetric cryptography" and "asymmetric key cryptosystem"  terminology?


texts: Hash coordinates (back-end) without the client (front-end) knowing the coordinates, but to be able to guess them

texts:
So I have a set of coordinates and I will hash these with a random salt with SHA256.
Coordinate range is 0,100.
salt = abc
[1, 5] = "sZv6eqPT9bqGiXbjvO8yrb4wuFjl0Z1CwSHdnIgGqEI="
[3, 4] = "8XgDJ/rrDELExVflBfDOLjqV5SB//8urxN5I6hxK9Mo="
[6, 3] = "FTzCfctBaBKp/wmopgMw7YFRpo1z2p6/IdHVujFliGs="
[1, 6] = "t2WE+ba8pt0ZEo0uW3uQH9FpI94tPVaICbctcl0YPtU="
[6, 3] = "FTzCfctBaBKp/wmopgMw7YFRpo1z2p6/IdHVujFliGs="

Input format is "{x},{y}".
Pastebin with C# code I used to generate this example: https://pastebin.com/yyMiYApc

So we have a back-end where we generate a list of hashed coordinates using a salt that just got generated. The idea was to send the hashed coordinates and the salt to the front-end. So they can verify a right coordinate using the same algorithm. If the generated hash in the front-end is like any of the hashes from the back-end, the coordinate is right. They have 20 attempts to guess all coordinates from the front-end. The idea was that the front-end would call the back-end with their coordinate and their assumption, the back-end would then verify their assumption and save it in the database. If they give faulty input we would ban / strike a user because of cheating.
We are creating a competitive guess game and we can't have 500ms delay from the back-end be a problem, so that is why we are letting the front-end make an assumption and let the back-end make the actual decision. Basically to remove input lag in UI.
This was a solid plan until we forgot that any client can decide to not call the back-end after they've verified a coordinate on the front-end. Thus making the number of maximum attempts redundant.
For example any client could brute-force all 10,000 possible coordinates and check what 5 are the right coordinates. Then call the verify in the back-end 5x and win the game.
We have real prizes for this game and want to make cheating impossible and at the same time remove the delay of calling a back-end to verify your answer.
I am in no way a cryptography expert. Is there any way cryptography could help us? And if yes, could you point us in the right direction? If this problem can't be sealed completely how could we make it very hard for the client to cheat?
Feel free to edit this question so cryptography experts understand it better!

Edit 1:
The reason the send the salt right now to the front-end is because the front-end needs to know whenever they have a right coordinate. So, like I explained before. There is no time to wait for the back-end to give feedback, because that would be too much input lag.
Whenever someone guessed an coordinate they should know this instantly. And not at the end of the game.


texts:
Edited (I removed the emphasize on Integers):

My question is partly cryptography and partly programming, I would appreciate any help on any aspect of it :)

I want to use PBC library to do the following operations:

Create a finite group, with "my custom" order ($Z_q$).
Choose a random value $g$ from this group.
Compute $g^r$, where $r$ is a random integer.

I tried to make the above work but I could not figure out to relate a finite group of my choice to this notion of pairing-based cryptography with no avail!

EDIT: Some more info on my problem:

In its simplest form, what I want to do is to choose $g$, $r_1$, and $r_2$, compute $g^{r_1}$ and $g^{r_2}$. To confirm the computation, I will later compute $g^{r_1+r_2}$ and compare it with multiplication of the previous values.

How can I achieve this in PBC?


texts: XOR cipher with fixed key and known relation among plaintexts

texts:
I have three messages, each known to be XOR-encoded, with the same key used for each message of this XOR cipher.

Encoded message 1: $e_1\,=\,00100111010$
Encoded message 2: $e_2\,=\,01001110110$
Encoded message 3: $e_3\,=\,11010110101$

I also have an extra information: I know that the decoded contents of $e_1\oplus e_2$ is equal to the decoded contents of $e_3$.
How would one go about solving this problem, in order to get the key and decode the contents of the message?


texts: NSA crack multiple encrypted channel by some tricks on 'Common DH Primes', which is a old news, but how actually they crack it? I still can't get the concept why using a 'Common DH Primes' will comprise a system. Can someone explain the process to crack a encrypted channel by using 'Common DH Primes'?


texts: Security of simple Skein PBKDF mentioned in the paper

texts:
From the Skein 1.3 paper section 4.8, Skein as a Password-Based Key Derivation Function (PBKDF), it mentions the following as a simple PBKDF (S = seed and P = password):

  An even simpler PBKDF is to simply create a very long repetition of S and P; e.g., S||P||S||P||S..., and hash that using Skein. (Any other optional data can also be included in the repetition.) This approach is not ideal with a normal hash function, as the computation could fall into a loop. But in Skein, every block has a different tweak and is thus processed differently.

The advantages I can see is that it is very simple to implement and hard to break the implementation accidentally.

Is this a more effective PBKDF than PBKDF2?

What about being more effective than Scrypt?

Is this a memory hard approach as well as CPU intensive? I imagine for a large length string e.g. 256 bit length seed + 256 bit length password (32 ASCII chars), repeated 100,000 times, this would force an attacker to use 6MB~ of memory to test one password. I imagine this could be easily customized to use the amount of memory required to be significantly slow for calculation and also require x MBs of memory per calculation.

What is a strong security level using this method? E.g. how many repetitions of the Seed and Password would be required? 100,000? 1000,000?


texts: Is this really a universal one-way function?

texts:
This PDF supposedly gives a construction of a universal one-way function, i.e. a function which is one-way as long as there exists a one-way function:

Recall that there are only countably many Turing machines (for any fixed alphabet).  Let $M_1,M_2,M_3,\dots$ be a list of all the Turing machines such that the length of the description of $M_n$ is bounded by some polynomial in $n$. Now, let
$$f_\text{univ}(x) = M^{(|x|^2)}_1(x)||M^{(|x|^2)}_2(x)|| \cdots||M^{(|x|^2)}_{|x|}(x)$$
where $M^{(|x|^2)}_{i}(x)$ denotes the output of $M_i$ on input $x$ right after $|x|^2$ steps of computation. One can verify that $f_\text{univ}$ can be computed in polynomial time. Now, suppose there exists a one-way function $f$. Then, there exists a Turing machine in our list, say $M_K$, that computes $f$. We note that for $x \in \left\{0,1\right\}^∗$ such that $|x| \geq K$, $f_\text{univ}(x)$ contains $M_K(x) = f(x)$. One can finish the proof using standard reduction techniques.

My question is, is this really a one-way function?  What if, say, $M_1$ was the identity function?  Then given $f_\text{univ}(x)$, wouldn’t it be trivial to get $x$, by taking the first however many bits of the output?


texts: How many random bits are required to create one RSA key?

texts:
If we were observing how many bits are taken from a random number source, what is the total number of bits required for creating a 4096 bit key using a current RSA implementation?
This means the total of the number of bits for finding the random primes P and Q, and the random number for the OAEP (padding), and any other random bits that might be needed that I'm not yet aware of.

Thanks!


texts: Is there a relation between passive/active attacks and IND-CPA/IND-CCA?

texts:
I've seen some papers drawing a connection between IND-CPA and passive attacks and IND-CCA and active attacks. Can someone explain how IND-CPA relates to passive attacks and IND-CCA relates to active attacks if this is indeed the case?
The most recent example of such a paper that I can recall is this: https://eprint.iacr.org/2020/1533
Another example is this excerpt from the preface of Introduction to Modern Cryptography, 3rd edition (http://www.cs.umd.edu/~jkatz/imc.html):
"We have divided our treatment of symmetric-key encryption into two parts:   Chapter 3 deals with security against “passive” attacks (i.e., CPA-security), while Chapter 5 addresses “active” attacks (i.e., CCA-security and authenticated encryption)."


texts: What are the reasons because of which ChaCha20 is immune to timing attacks ? Also why is not AES immune to timing attacks?


texts: Why the permutation of the right hand rotor given in Rejewski's paper is $PNP^{-1}$?

texts: I would like to know why the permutation of the right hand rotor given in Rejewski's paper  is $PNP^{-1}$. First of all I can't get how he added an $P$(alphabetic permutation) at the front of $N$(right hand rotor permutation) when there's no alphabetic permutation taking place before the current enters the first rotor permutation. As far as my knowledge goes I think there's only a plugboard swapping that takes place. Second I can't get how an inverse permutation takes place before the current through $N$(right hand rotor permutation) enters the middle hand rotor.


texts: Key length requirement in a simple XOR implementation

texts:
I don't have much previous experience at all with cryptography, this is pretty much the first time I've tried anything similar.

I'm trying to implement an extremely simple XOR encryption system in ComputerCraft for fun, here is the code:

local function xorEncrypt(data, key)
    local klen = #key local
    s = ""
    for i = 1, #data do
        s = s..string.char(bit.bxor(string.byte(data, i), string.byte(key, i % klen)))
    end
return s
end

The only thing I need to know is, in this case, will the messages still be able to be decrypted if the key that I use is shorter than the data I am encrypting?


texts:
zendo is a new mobile phone app which encrypts messages using a one-time pad:

http://techcrunch.com/2015/03/24/one-time-pads-ride-again/

users have to meet in person and exchange a key via a qr code. the one-time pad data is then initialized on both phones using this key to make a secure transfer. however, according to the article, only 0.5MB of pad data is exchanged:

  The process takes a few seconds for 0.5MB of pad to be exchanged —
  which is enough for “thousands” of messages between the two users.
  More than 3,000 based on a conservative estimate of average text
  message length, according to Newbold. You can also exchange multiple
  pads to stockpile more megabytes for even more future missives. (To be
  clear, if users run out of pad, the app defaults to AES encryption so
  messages are never sent unencrypted — it just steps down to industry
  standard levels of security.)

  Pictures can also be sent via Zendo, and those are encrypted with a
  single use AES 256bit key and an HMAC key (for authentication), which
  are then sent using One-time pad encryption, so the photos are secured
  via OTP without needing to use up too much of the pad to send them.
  The same method will be used to encrypt and send videos, audio and
  documents/attachments — file transfer features which will be coming in
  future updates to the app.

it was my understanding that a one-time pad must be as long as the plaintext being transferred, so 0.5MB of pad would enable no more than 0.5MB of plaintext to be transmitted with perfect secrecy.

however the above excerpt makes it sound like the pad can be shorter than the plaintext while still maintaining the complete security of a one-time pad:

  so the photos are secured via OTP without needing to use up too much of the pad to send them

i'm just wondering if this is some cryptographic technique that i have not heard of, or if the article is wrong to imply that the cyphertext will have the same security (entropy) as the pad, for data that is longer than the 0.5MB pad (as most photos and videos are)?

edit

my problem was actually with the wording of the article. i was reading the above quote as:

  Pictures can also be sent via Zendo, and those are encrypted with a
  single use AES 256bit key and an HMAC key (for authentication), [the
  pictures] are then sent using One-time pad encryption, so the photos are
  secured via OTP without needing to use up too much of the pad to send them.

but actually i think the article means to say:

  Pictures can also be sent via Zendo, and those are encrypted with a
  single use AES 256bit key and an HMAC key (for authentication), [the aes
  key and hmac key, but not the pictures] are then sent using One-time pad
  encryption, so the photos are secured via OTP without needing to use up too
  much of the pad to send them.

and this makes a lot more sense.

sorry this turned out to be more of a reading comprehension question than a cryptography question in the end :p

i don't want to add another question now as that would be unfair to those who have already given answers addressing my first misunderstanding-question. thanks.


texts: Are parts of a pseudorandom string also a pseudorandom string?

texts:
I am working on an exercise that encrypts a message using only the first $n$ bits of a pseudorandom generator's output $G(k)$, i.e. $F_k(m) := G(k)_{0...n−1} \oplus m$.

$k$ is chosen uniformly at random and $k, m \in \{0, 1\}^n$.
My task is to decide whether an encryption scheme based on $F_k$ can be secure against a ciphertext-only attack, a CPA attack and whether it's indistinguishable.

My idea was that, if $G(k)_{0...n−1}$ is still a pseudorandom string, the exercise reduces to the case of using the whole output of $G(k)$. Then the scheme would be secure against a ciphertext-only attack and indistinguishable, but not secure against CPA attacks since it's a deterministic scheme.

My problem is that I couldn't find out, whether $G(k)_{0...n−1}$ can be treated exactly like the entire output of $G(k)$. Furthermore, I am not sure whether my intuition about solving the exercise is right. I would appreciate any hints!


texts: Patterns in elliptic curve division polynomials

texts:
While looking at division polynomials of elliptic curves in relation to this and this questions, I noticed some patterns. I am wondering if anyone knows of general formulas the describe these patterns. First, an example:

Suppose we have an elliptic curve defined by $y^2 = x^3 + 2x + 10$ over $\mathbb{Z}_{q}$ where $q=53$. The order of this curve is $p = 59$. Suppose also that the generator $G = (7, 7)$.

For any value $a$ in $\mathbb{Z}_{p}$ we can build a sequence of a values generated by evaluating division polynomials such that:

$$
a_0 = \psi_a(G)
$$

$$
a_1 = \psi_{a+p} (G)
$$

$$
a_2 = \psi_{a + 2p}(G)
$$

$$
a_i= \psi_{a+ip}(G)
$$

The table below shows these sequences built for various values of $a$ (columns with values for $a$ between 4 and 16) and $i$ (rows with values for $i$ between 0 and 27):

My questions are:

It seems like the sequence $a_0...a_i$ is periodic (in the example above, it repeats after every 26 values of $i$). It also seems like the length of the period depends only on values of $q$ and $p$ (and not on the equation of the curve). Is there a general formula that can be used to calculate the period of the sequence for arbitrary values of $q$ and $p$?
It seems like within each period, there are two points of symmetry where the preceding value equals the following value. In the above table these points have light orange background (e.g. for $a = 4$ these points are $a_5 = 36$ and $a_{18} = 20$). Is there a general formula that can be used to find such points of symmetry?
It also seems that these points of symmetry have some relation to quadratic residue modulo $q$. For example, in the table above, exactly one point of symmetry is a quadratic residue modulo $53$ (these points have borders around them). Is there a general formula that describes this relation?


texts: Cryptography — with a semi-priveleged user in the middle — to prevent request-tampering with another server

texts:
I'm working on a chat server for a mobile app I am writing. I would like to use a different application server for non-chat related operations and another application for chat operations.

I would like to encrypt the user's id, the user's username, and the name of the chat stream and pass those to the client—and store that in a key on the client (call it ChatKey). From there, the client sends the ChatKey and their message to the chat application server. The client also can fetch messages from the specified stream with the ChatKey. This communication is done over HTTPS.

Why encryption at all? I don't want the user to be able to spoof their username, their id, or the chat stream when communicating with the chat application server. But I also would like to reduce overhead: I do not want the main application server to have to broker communications with the chat server.

I am wondering:

1) does this implementation make sense?
2) is symmetric cryptography okay?
3) which package is good to use? there are so many out there and I am lost! In particular I am interested in packages in Go and Python (RSA? ECDSA?)

The private key would only reside on the main application server and the chat application server.

Thanks!


texts: What is the probability to produce a collision under two different hash functions?

texts:
Given 2 (weak) hash functions, namely MD5 and SHA1

The fact that there exists 2 different inputs that will result in the same output under both hashing functions is explained in "Can there be two hash functions without common collisions?"

I would like to quantify the probability of this type of inputs to be forged.
Namely:

MD5(x) = MD5(y)
whilst
SHA1(x) = SHA1(y)

So if I keep the two hashes of a file, how much harder is it to forge another file that yield the same hashes rather than either of those individually ?

I expect it to be more than the added probability of each, but by how much (order of magnitude) ?


texts: How can I generate a brief (100) stream of random numbers, not using the computer or throwing dice?

texts: I am looking for a method of making random numbers that is off-line and is also independent of specialist equipment like a Geiger counter.


texts: Authentication by hardcoding public key in client software

texts:
It would seem to me that mobile applications could reduce network traffic by hardcoding the server's public key into the app.

The idea being that they could then encipher a secret to share with the API using the public key.

We then would seemingly not need to validate the server-side identity, because only the private key holder should be able to decrypt the message.

The conversation could then switch to symmetric encryption immediately, since both sides have knowledge of the key.

Apart from key management issues, in the event of an unrelated private key compromise, is this otherwise secure? What weaknesses, if any, are there for this scheme vs. traditional TLS handshake?


texts: What scheme will allow merging and splitting the result of a function?

texts:
I am wondering if it's possible to have a scheme as follows.

Here is the scenario:

we have a set of objects (e.g. strings) {O1, O2, ..., On}
we have a set of users {U1, U2, ..., Um}
each user asks to compute a special function f over a subset of the objects
we have an intermediate (trusted) component A that must be able to merge requests coming from different users into one single request
we have a third (untrusted) component B that computes f over the objects contained in the request sent by A
A must be able to split/derive the result of the function for the request of each user

I am looking for a function f that would satisfy this scheme

All requests and results should be encrypted and no key is shared among users.

A is trusted. B is NOT trusted.

By merge I mean that the resulting request should be a request to compute the union of all the subsets contained in the users' requests.

B must not know which request came from which user.

This scheme does not need to be able to handle arbitrary functions.

Here is a practical example:

There are three users U1, U2 and U3 and a set of objects {O1, O2, O3, O4, O5}

U1 requests to compute f(O1, O2)
U2 requests to compute f(O1,O2,O3)
U3 requests to compute f(O1,O4,O5)
A receives these three requests and creates a new request to compute f(O1,O2,O3,O4,O5) which is the union of the requests sent by users.
B computes f(O1,O2,O3,O4,O5)
A receives f(O1,O2,O3,O4,O5) and somehow is able to derive f(O1, O2) for U1, f(O1,O2,O3) for U2 and f(O1,O4,O5) for U3

Is there any scheme which will allow me to achieve what I explained above?


texts: Is the length limit of AES-GCM per key or per (key, nonce) pair?

texts: AES-GCM has a limit on the length of the plaintext it encrypts: $2^{39} - 256$ bits. But is this limit per key or per (key, nonce)? That is, if I encrypt a message with the maximum length, and encrypt another message with the same key but different nonce, will it be secure still?


texts:
Could you please explain what the pipe (|) in tor specification means -- is it a bitwise or or a concatenation of the values?

  Encoding onion addresses [ONIONADDRESS]

  The onion address of a hidden service includes its identity public
  key, a    version field and a basic checksum. All this information is
  then base32    encoded as shown below:

  onion_address = base32(PUBKEY | CHECKSUM | VERSION) + ".onion"

  CHECKSUM = H(".onion checksum" | PUBKEY | VERSION)[:2]

  where:

  PUBKEY is the 32 bytes ed25519 master pubkey of the hidden service.
  VERSION is an one byte version field (default value '\x03')
  ".onion checksum" is a constant string
  CHECKSUM is truncated to two bytes before inserting it in onion_address

From the context, I understand it is a concatenation-- is that so?

If one has a working short Python\Node\Ruby snippet for that, it would be lovely.  :)


texts: Pseudorandom number generation predictability

texts: Can you expect with certainty that any pseudo-random number generator will produce the same stream with a shared seed?


texts: How slow is the hash used for Mac FileVault encryption?

texts:
Certain password strength estimators (for instance, zxcvbn) give estimates that vary with the speed of the hash and the assumed resources of the attacker. I am curious what hash is used by the MacOS FileVault encryption on MacBooks, and whether it should be considered a "fast" or "slow" hash for the purpose of estimating the speed of an attack on it.

More specifically, how many hashes per second could a good modern GPU perform, for the purpose of cracking a password protecting a FileVault drive?


texts: Can anyone explain how the modified r-adding walk works?

texts:
I was going through a paper titled “Accelerating Pollard's Rho Algorithm on Finite Fields” by Jung Hee Cheon et al. I understand the table(Ml) creation part of it, but after that I somehow fail to follow the rest.

Can anyone explain the modified r-adding walk to me?


texts: Construct an Oblivious Transfer protocol using a secure protocol that outputs random bits between two sides

texts:
Assume that there is a protocol $(A,B)$ such that receives no input and satisfies:
$A$ - outputs two random bits $x_0, x_1 \in \{0,1\}$
$B$ - outputs a random bit $b \in \{0,1\}$ and also outputs $x_b$
Saying that $(A,B)$ is secure means that $A$ doesn't learn what is $b$, and $B$ doesn't learn what is $x_{\lnot b}$
Now, I need to construct a secure Oblivious Transfer protocol $(S,R)$ using $(A,B)$.
At first, I didn't really understand why I can't just plainly use $(A,B)$ as the Oblivious Transfer protocol, but I guess that since the outputs of $(A,B)$ are random and don't use any input, so it's not really an Oblivious Transfer protocol.
So my idea was to somehow use the output of $(A,B)$, namely $x_0, x_1, b$ as keys in an encryption system that will be used to pass input between $S$ and $R$. I want to use the simplest encryption, so One Time Pad will work for me.
However, I am not sure how exactly construct $(S,R)$, when to use $(A,B)$ and when to use the One Time Pad.
I know that are Oblivious Transfer protocols based on $RSA$ or $DDH$, but I don't think that I need to use them when $(A,B)$ is given to me.
Help would be really appreciated.


texts: Determining if Server/Client's TLS configuration is Vulnerable to SLOTH

texts:
In the context of SSL/TLS protocol and SLOTH vulnerability. I want to find out if certain websites(webservers) or applications that use TLS are vulnerable. I need some guidance for this.

My idea is to develop/find a tool(maybe openssl) that connects to the servers and in the client hello asks for RSA-MD5 SignatureAndHashAlgorithm to test if the server sends the corresponding certificate under this configuration and conclude that the server is vulnerable.

Likewise for the client certificates, I want to ask for client certificates signed by RSA-MD5 and if the client sends its certificates under this setup I'll conclude that the client is vulnerable to SLOTH.

First, is my approach right? or am I off the road?

Second, what types of tools do I need to use? Is openssl capable of producing such requests and responses?


texts: Average case problem and worst case problem in lattice

texts:
In Regev's lecture there is "In contrast, virtually all other cryptographic constructions are based on some average-case assumptions.
For example, in cryptographic constructions based on factoring, the assumption is that it is hard to factor
numbers chosen from a certain distribution. But how should we choose this distribution? Obviously, we
should not use numbers with small factors (such as even number), but perhaps there are other numbers that
we should avoid? In cryptographic constructions based on worst-case hardness, such questions do not even
arise."

I do not understand the meaning of "In cryptographic constructions based on worst-case hardness, such questions do not even arise." According to my understanding, in cryptographic constructions based on worst-case hardness we based the cryptography scheme on hard subsets in which the problem is hard, so we should also avoid we based the cryptography scheme on subsets in which the problem is easy.


texts: Standard tools for deterministic RSA key generation using seed?

texts:
I'd like to resuse the mnemonic I have from bip39 for crypto in other domains such as ssh and tls, etc.  Are there standard tools (ie, openssl) to deterministically generate rsa key/pairs given a seed value?  I know technically it is possible using PBKDF2 to create a PRNG etc, but I'm definitely not looking to roll my own crypto.
I'm just wondering if there is an easy way using openssl or gnu to reuse my bip39 mnemonic in other contexts besides crypto.  Or if there is a way of converting the derived key pairs from one algorithm into rsa using standard libraries.
Thanks.


texts: Finding algorithm: desire RSA's uniqueness and ECDSA's space efficiency

texts:
I am asking for help in finding a signature algorithm with the following property:

Given a message m and a private key prikey, the result of signing m with prikey is unique (which is stricter than deterministic). In another word, there is only one signature (or finding another one using prikey is securely hard) that can pass the verification by the public key of prikey.
High space efficiency of storing private key and signature.

ECDSA's space efficiency is satisfying, but the signature is not unique; RSA has uniqueness, but is there any alternative with better space efficiency?


texts: During padding oracle attack (CBC), how is first byte of plaintext block is obtained?

texts:
Imagine conducting a padding oracle attack against CBC mode with 16-byte length blocks, and PKCS#5 used for padding.

You start, as always, revealing the last byte of plaintext. Then you iteratively move backward and reach the first byte of last plaintext block. At this stage, you already spoofed the padding with 15 bytes, which values are 0x0f.

So, how do you reveal the first byte of a block, since you’re out of padding length?
Does PKCS#5 allow you to pad 16 bytes with 0x10 value?
Or, these things are up to the implementation of padding used in a specific application?


texts: Minimum number of independent trials needed to detect a bias

texts:
Suppose, I suspect that the probability of occurrence of a particular bit as $0$ is $.558$. Since, it is not $.5$, so this is possibly a bias. Now, my question is:

  What is the minimum number of independent trials I need to confirm my result?

I mean, observing this scenario for, say 100 times, must not be convincing. There should be a theoretical result regarding this. It would be very helpful if someone links such papers while answering.

What I am looking for is: Suppose I suspect a possible bias of $0.5 \pm x$, $x \in (0, .5]$. Then, at least, say $2^{1/x}$ trials are need to confirm my suspicion.

Related: https://stats.stackexchange.com/questions/417981/calculate-the-number-of-trials-needed-to-achieve-certain-number-of-successes-at


texts:
Apologies for the obviously ridiculous question but I need to know where I'm going wrong here.

For RSA, we compute $n=pq$ for primes $p$ and $q$. We then choose an $e$ such that $gcd(e, \varphi(n))=1$ and compute $d$ such that $ed = 1 \mod \varphi(n)$. The public key is $(n, e)$ and private key is $(\varphi(n), d)$. I see how this is correct and so on.

My question is this: Why doesn't an attacker just compute $d'$ such that $ed'=1 \mod n$? Then surely decryption will work mod $n$?

eg where does this go wrong? $e=3, p=11, q=17, n=187, M=2$ Then $C=M^3=8$ Attacker calculates $e^{-1} \mod n = d' = 26$ and $8^{26}= 2 \mod n$?? More generally $C=M^{ed'} \mod n = M^{1} \mod n = M$?


texts: Is it possible to retrive the Hash from an encrypted folder?

texts:
So first of all I've a software which basically locks/encrypts a folder with a given password. Afterwards it's almost impossible to open the folder without entering the password through the software.

I locked some of my much needed files and accidently forgot the password.

So my question is, is it possible to retrive the hash from the encrypted folder? I'm planning to brute-force if it's possible.

If it's not, then should I reverse engineer the software to open the encrypted folder without entering the password?

What other possible options do I have?


texts: Why isn't Kerberos using temporary keys to avoid dictionary attacks?

texts:
In the Kerberos protocol, the user sends his ID, the server (Or ticket granting server) ID and a nonce value. The Key Distribution Center uses a key (I assume symmetrical) derived from the client's password to send a message containing the session key between the client and the server and the same nonce. It also sends the ticket non-encrypted.

This exposes the protocol to dictionary attacks if the password is weak. An attacker can try to decipher the message sent by the KDC using the dictionary passwords and verify the result by checking if the nonce value is there.

I'm learning the Kerberos protocol and I'm confused by this weakness. It wouldn't be difficult to use the key derived from the user's password to establish a Diffie-Hellman key, and send the same message encrypted by the established key.

It completely solves the dictionary attack problem, and I can't see any downside.

Am I missing something?


texts: Can I find a specific SHA512 for an partially-known string?

texts:
I have a plain text string "I-like-drawwing", and this string has a SHA512 value, assume the SHA512 is "aabbcc".
Then I show SHA512 "aabbcc" to my friend and say:
"this is SHA512 for my string,
and my string ended with 'ing',
I bet $20 that you don’t know my string".

I don't want loose, so I must find another string ended with "ing" and also has the same SHA512 "aabbcc",
Can I find that string?


texts: Is there a rule of thumb for ZK protocols?

texts:
There's always a small chance for many zero knowledge protocols that the prover had a lot of luck to prove something to the verifier.

Take the Ali Baba cave as an example:

The prover has a 50% chance of guessing the side of the cave correctly. That's why the procedure has to be done multiple rounds for the probablility of the prover not knowing a secret becomes reasonably small.

In this example the probability of guessing something correctly is $2^{-n}$, where $n$ is the number of rounds.

My questions are:

Is there a rule of thumb for how small this probability has to be?
What's the value of this probability in today's ZK protocols?


texts: Assistance with Permutation Cipher (Columnar Transposition)

texts: I was wondering if someone could provide some assistance with understanding a permutation cipher.  I have both the cipher text as well as the plaintext but am having some difficulties trying to find the period (or key).  What are the steps to locate the key? This is the cipher text:


texts: Why can ssh-keygen export a public key in PEM PKCS8 format?

texts:
In the documentation of ssh-keygen (man ssh-keygen) it says for the option -m that an export to the format “PKCS8” (PEM PKCS8 public key) is possible.

That works, and I can read the files using openssl. But the thing that really confuses me: isn't PKCS#8 a format for private keys?

Or is PKCS#8 a format for the keypair, and the private key is omitted? Those formats are really confusing.

Here is an example key exported with ssh-keygen -m PKCS8 -e:

-----BEGIN PUBLIC KEY-----
MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEAuRKdrvmS/1FdSvzljmq8
jNEAPMLLxuTT+yCAw5gZ5VaXQ6BR1LudV2N6YOFYp7yUoOye3CobHI9GhAXrNaHr
S3XoMk7/49g/uNNjJUTPzQ1xXZRbTnRgOkAbstYZDWY53S8X8fqk6ET0h3q2VwTu
vkNkzZpiswkSFi7/SqLF0P+DEewyDTeywaGTUO4ls+8nTtl+T63LRSBGd8qUdOzg
nfhr/YosKg3ePFyw1uC2UCK65KG47kmext+rLGFXT1o8oZ/Mlw5e+0aVSEoa6+MG
vXmhdV0IURnw/DJlalisxppFDHjyg6amBqC08w7r1nooqZvnjCXiXR+LEPlfj6hm
1wIDAQAB
-----END PUBLIC KEY-----


texts: Is it possible to recover the seed value from a Mersenne Twister PRNG state?

texts:
So I know that you can recover the state of a mersenne twister generator by observing a sequence which is long enough.

I was wondering if you could be able to recover the actual seed value used or if an attempt would yield an equivalent at best?

Also, closely related, let's say we use a 32-bit seed value. Does this mean that a mersenne twister generator could yield $2^{32}$ different sequences for each unique seed value or are there seeds which produce the same sequence?


texts: Perform ENT / Dieharder on raw entropy or on whitenened entropy?

texts: In this question about hardware random number generator, a discussion about the following question has been started: In order to test RNG's and entropy's quality, should test suites like ENT and Dieharder be applied on raw entropy or on whitened entropy?


texts: How can mega store my login details and still be secure?

texts:
I understand how Mega's encryption works. For a quick summary of all those in the future looking for an answer on this... here is how it works:

Upon first signing up for an account you make a username and password. It also generates a symmetric key which is used to encrypt your files and a RSA key pair to share secrets securely when files are sent to other peoples "inboxes". Once the client has both these, the symmetric key is encrypted with your password and uploaded to the server. This way only someone with your password can decrypt your symmetrical key and then decrypt your files. I'll leave it at this for now as thats all that is relevant to my question.

If my symmetric key is encrypted with my password, no matter how secure my key is would it not still be as weak as the hashing function they use to store my password on their server? This ties into my second question, do they even store a hash of my password? I'm thinking along the lines of no, as it would weaken the encryption hugely, but Mega still needs to be able to determine if your login details are correct. How can they do this without compromising their encryption?

This may be the wrong place for asking this, so please move it if appropriate.


texts:
What is "Perceptual Encryption", and where do we use it?

I came across it whilst reading a paper on ECC in a multimedia context, from which I quote:

  Hence, to achieve perceptual encryption, the higher-order biplanes were selected to be encrypted.

In addition to a formal definition, I would appreciate some examples of using it.


texts: Is there any definition for "generic attack" in context of cryptography or more specific "hash functions"?

texts:
I'm searching a definition of "generic attack" in context of cryptography or more specific in context of "hash functions". I searched some books and the web but I did not found any definition for it only the usage like "generic birthday attack".

Does someone have a definition for that or knows where I get one?


texts: Is it possible to get different plaintexts from a single ciphertext using different keys?

texts:
Suppose to have a chipertext that you can't decrypt, but you know that the plaintext can be A, B or C. Then arrives to you the key which is used to encrypt the chipertext.
You can decrypt the chipertext and you get a plaintext equal to A. Is it possible that the original plaintext was B or C and you have received a key such that the decryption process gives as output a different plaintext (A)?

Of course, each A, B and C have a meaning to you, so if you decrypt something else (like D, E, F...) you understand that it is meaningless. Also, i want to add that the source from which you receive the key cannot be trusted, but this doesn't mean that the key is always incorrect.

For clarification:

I receive a ciphertext I can't decrypt
I receive a key to decrypt the ciphertext
I decrypt the ciphertext with the key from step 2 and get the plaintext

How can I be sure that the plaintext obtained is infact the one previously encrypted if I can't trust the source from which I get the key and the ciphertext?


texts: Would the result of encrypting weak random data via AES-128 with a CSPRNG-generated key be considered strong/secure random data?

texts:
I am trying to understand the security implications of using a well known block (or stream but in this example block) cipher like AES-128 to produce pseudo-random data.

My specific question is would the output of the following be considered cryptographically strong pseudo-random data:

Generate an AES-128 key using a CSPRNG.  (An IV would of course be securely generated as usual.)
Seed an MT random number generator from a CSPRNG.
Encrypt a stream of bytes from this MT source with AES-128 using the key above.  (Perhaps the MT source is unnecessary, encrypting zeros might do just as well?)
Use the resulting bytes as pseudo-random data (for generating unique IDs that are "hard" to guess).
Every so often reset the above and start over from new CSPRNG data.

The goal is to have something that is still cryptographically strong but faster to generate than using the system's CSPRNG.  To answer the question ahead of time, yes I have timed it and /dev/urandom and other system CSPRNGs are significantly slower than the performance I'm looking for. (EDIT: I think I screwed up on my benchmarks, the Go standard library uses /dev/urandom and now I'm seeing it does give results in the 2-digit nanosecond range - very fast, so possibly I'm overkilling here.  The question remains valid though.) Thus what I'm looking to understand is the security implications of doing the above.  Is there anything I'm missing about this idea or that I should be aware of in terms of potential pitfalls?  Is there a particular cipher mode that is well-suited to this use?  As far as I understand it, encrypting unknown input using a securely-generated key with a not-known-to-be-broken cipher like AES should result in cryptographically secure pseudo-random output.  Is that a correct assumption?


texts: Publicly verifiable secret sharing scheme

texts:
In https://www.win.tue.nl/~berry/papers/crypto99.pdf, Schoenmakers proposes a publicly verifiable secret sharing scheme, that uses a non-interactive DLEQ proof to allow any participant to verify the shares of the secret (section 3.1 of the paper).

In "Distribution of the shares", it says "Applying Fiat-Shamir’s technique, the challenge $c$ for the protocol is computed as a cryptographic hash of $X_i , Y_i , a_{1i} , a_{2i} , 1 ≤ i ≤ n$."

And later, "Using $y_i , X_i , Y_i , r_i , 1 ≤ i ≤ n$ and $c$ as input, the verifier computes $a_{1i} , a_{2i}$ as

$$a_{1i} = g^{ri} X_i^c,$$ $$a_{2i} = y_i^{ri} Y_i^c ,$$

and checks that the hash of $X_i , Y_i , a_{1i} , a_{2i} , 1 ≤ i ≤ n$, matches $c$."

My question is: how can the challenge $c$ be used as input of the hash that computes itself (the challenge $c$), or am I misunderstanding?


texts:
I'm signing mails with the RSASSA-PSS (p1v2.1) certificate. When I click Details, it shows "Signature Algorithm: RSASSA-PSS".
openssl x509 -text shows
    Signature Algorithm: rsassaPss
     Hash Algorithm: sha256
     Mask Algorithm: mgf1 with sha256

certutil -dump shows:
1.2.840.113549.1.1.10 RSASSA-PSS

Now, whem I send my signed emails and click on Details in outlook, it shows "Signature Algorithm: RSA (2048)"
I'm using bouncycastle for signing and when I use "SHA256WithRSAEncryption" it works fine, but when I'm using "SHA256WithRSAAndMGF1" Signature, Outlook tells me "The digital signature on this item is Invalid or Not Trusted." and when I click details, I see "Signature Algorithm: RSA (2048)".
Is p#1v2.1 still not supported by outlook/microsoft or am I just crazy?


texts: Could ANY cipher serve as the foundation for a public key cryptosystem?

texts:
My reasoning goes like this:

In principle, any trapdoor function can serve as the foundation for
an asymmetric encryption scheme.
All ciphers are trapdoor functions, since it's easier to encrypt plaintext than it is to crack ciphertext.  Put another way, it's easier to use key and plaintext to produce ciphertext, than it is to go backwards and use ciphertext to produce key and plaintext.
Therefore, one could (at least in theory) devise a public key
cryptosystem derived from any cipher, whether it be Caesar or AES.

This has the interesting implication that one could devise an asymmetric encryption scheme based on an existing asymmetric scheme + key + plaintext combo, and then derive another from that one, etc. etc.

I found this interesting quote which seems to confirm my hunch:

  every problem X in NP has a naturally associated public-key cryptosystem (warning: it's a .PDF file)


texts: Is there a reason behind the number of bit rotations used in SHA-256?

texts:
SHA-256 uses the following bitwise functions during the hash algorithm:

$$\begin{align*}
\Sigma_0^{\{256\}}(x)&=\operatorname{ROTR}^{ 2}(x)\oplus\operatorname{ROTR}^{13}(x)\oplus\operatorname{ROTR}^{22}(x)\\
\Sigma_1^{\{256\}}(x)&=\operatorname{ROTR}^{ 6}(x)\oplus\operatorname{ROTR}^{11}(x)\oplus\operatorname{ROTR}^{25}(x)\\
\sigma_0^{\{256\}}(x)&=\operatorname{ROTR}^{ 7}(x)\oplus\operatorname{ROTR}^{18}(x)\oplus\operatorname{SHR}^{ 3}(x)\\
\sigma_1^{\{256\}}(x)&=\operatorname{ROTR}^{17}(x)\oplus\operatorname{ROTR}^{19}(x)\oplus\operatorname{SHR}^{10}(x)\end{align*}$$

Is there are reason behind the number of circular right shifts (ROTR) each of these functions use? I'm guessing its to try and "scramble" the bits as much as possible, but why for example does Σ0 use rotations of 2, 13, and 22?

Is there an actual reason, or are they arbitrary?

I notice each function uses a prime number for at least one of their rotations, but aside from that I haven't been able to find a reason for the numbers. The specification doesn't seem to explain why.


texts:
How and why do we face a problem when encrypting values of 0 and 1 using the RSA cryptography Algorithm?
Is there any way to solve it?


texts: How does ECDSA signature verify work in EOS and ETH/BTC, compare to standard (on text book I mean)

texts:
I have been studing ECDSA signature/verify for a while. By my understanding: the standard ECDSA signature/verify process (which we find on text book) are like below:

- A sender combines message and its ECC public key (pk), do hash, then using ECC sk (private key) to generate signature; it then append the signature with the message (ECC pk include), send all these to receiver;

The receiver do ECDSA verify by using the ECC pk, the message and the signature output true or false;

Question1: for EOS signature verify process looks not likely align to a standard ECDSA signature verify above:

A EOS node may need do two kinds of ECDSA signature verify:

1). Check each Tx signature--from code it use a routine naming as get_signature_keys, indicate it recovers the pk? Then follow up by a routine naming as check_authorization (this does not like a real signature verification, I couldn't understand what a "check authorization" means--by all mean it does not like a signature verify);

2). Check a Block's signature, this routine (name as "verify_signee") however, looks likely a real ECDSA signature verify.

Question2: I know BTC/ETH may adopt quite different method as they are PoW so each miner must do signature verification for each Tx inside a block, but as they have much more time (several minutes) than in EOS, they would be using the standard ECDSA verification?


texts: Visualization of Elliptic Point Addition

texts:
In an introductory text, I found that point addition for elliptic curves can be made plausible as follows:

Given two Points, P, Q, the sum is defined as the point on the curve I get by connecting P with Q with a straight line. This line intersects the curve on a third point. After reflecting y I get the sum P+Q.

However, taking the points R and Q on the attached figure $y^2=x^3-\frac{29}{10}x +1$, where is the third point?

Should it be the point at infinity?
That cannot be from my point of view, because $P+Q=\infty$ would imply $P = -Q$ which is not the case.

See also:

http://demonstrations.wolfram.com/AdditionOfPointsOnAnEllipticCurveOverTheReals/
The Snapshot 1 is the curve I talk about. The following is stated below:

  For two points P and Q on an elliptic curve, the addition is defined as follows. Draw the line through P and Q to intersect the curve in a third point; then reflect that point in the  axis.


texts: How to recover $e$ from $f_A(e) = Ae \mod q$ when knowing trapdoor

texts:
I have a silly question, but I don't know a solution, so I need to question.

Assume, with a algorithm $TrapGen(1^\lambda)$, it generates $A\in\mathbb{Z}_q^{n\times m}$ with a basis $B \in\mathbb{Z}_q^{m\times m}$ for $\Lambda^\perp(A)$.

With ISIS problem (inhomogoneous small integer solution), if $SIS_{q,m,2r\sqrt{m}}$, define a function $f_A(e) = Ae \mod q$ where $\Vert e \Vert \leq r\sqrt{m}$, how to recover $e$ when we know $A$ and $B$, and is this solution unique?

$TrapGen$ is defined in  Generating Shorter Bases for Hard Random Lattices


texts:
I´m stuck in my homework and since its homework, I would rather get some hints than full solution. The problem goes:

factorize n = 88416763 in case that you know that the square roots of
51733469 (mod 88416763)
are 50224876, 38191887, 22222, 88394541.


texts: Non-interactive zero-knowledge proof for discrete logarithm without random oracle

texts: Is there any non-interactive zero-knowledge proof for discrete logarithm without random oracle over the group $\mathbb Z_p$?


texts: Calculating RSA private exponent when given public exponent and the modulus factors using extended euclid

texts:
When given $p = 5, q = 11, N = 55$ and $e = 17$, I'm trying to compute the RSA private key $d$.

I can calculate $\varphi(N) = 40$, but my lecturer then says to use the extended Euclidean algorithm to compute $d$. That's where I get stuck.

Here's my work so far:

First I use the Euclid algorithm to calculate:

40 = 2(17) + 6
17 = 2(6) + 5
6 = 1(5) + 1 = gcd

So I know the GCD is 1. Applying the 'extended' section of the algorithm:

6 = 40-2(17)
5 = 17-2(6)
1 = 6-1(5)
1 = 6-1(17-2(6))
3(6) = 1 (17)
3(40 - 2(17)) - 1(17)
3(40) - 3(17)

I know the answer is $33$, but I have no idea how to get there using the extended Euclidean algorithm. I can't figure out why I'm getting $3(40) - 3(17)$ when I know the answer should contain $33$.


texts: Are there any known vulnerabilities in SHA-1 that can be exploited? Certain patterns that it shows? I recently performed a frequency analysis using 20,000 common words, and found nothing exploitable. What others techniques can I use to assert the security of SHA-1?


texts: How to generate a ciphertext independently decodable with multiple keys?

texts:
Is it possible to encrypt a message in such a way that multiple keys can independently decrypt it?

In other words:

Having knowledge of $key_1, key_2 ...key_N$, which are different symmetrical keys, is it possible to generate a ciphertext that can be independently decrypted using either $key_1$ or $key_2$ or $key_N$, in such a way that the length of the ciphertext is less than directly proportional to $N$?


texts: ElGamal Signature Scheme: Recovering the key when reusing randomness

texts:
Show how if Alice uses the same value of $k$ to sign two different messages $m_1$ and $m_2$, using the ElGamal signature scheme, Eve can recover the value of $a$ from the corresponding signatures $(m_1, r_1, s_1)$ and $(m_2, r_2, s_2)$. (Note: you are allowed to assume that if $\gcd(a, n) = d$ then there are $d$ solutions to the congruence $ax \equiv b \pmod n$.)

  ElGamal Signature Scheme:

  Key Gen:

  Compute $y = g^x \;\bmod p$.

  The public key is $(p, g, y)$. The secret key is $(p, g, x)$

  Signature Gen:

  Choose a random $k$ such that $0 < k < p − 1$ and $\gcd(k, p − 1) = 1$

  Compute $r = g^k \;\bmod p$ and $s = k^{-1}(m – xr) \;\bmod{p-1}$

Thoughts: So far, I can tell that $r_1$ and $r_2$ are equal and $s_1$ and $s_2$ are closely related since the only variation is $m$.

We can relate the two equations for $s$, by solving them for $-xr$:

$$s_1k - m_1 \equiv s_2k - m_2 \pmod p$$

$$(s_1 - s_2)k \equiv m_1 - m_2 \pmod p$$

Let $a = s_1 - s_2$, then we know from the question that for $\gcd(a, n) = d$ there are $d$ solutions for $k$.

Now the forger can compute $g^k$ for each solution to k, until $r$ is found.

Then compute $xr \equiv m_1 - ks_1 \pmod{p-1}$

There are $d' = \gcd(r, p-1)$ solutions for $x$.

The forger can compute $g^x$ for all the $x$s found until she finds $y$.

Once she has $y$ she knows the proper $x$ which can be used to find $m_1$ and $m_2$.

How does this look?


texts: A combination of game-based and simulation definitions to analyse a protocol security

texts:
Consider the case we want to design a crypto protocol: $P_1$, say for verifiable computation. We define the protocol by designing a game and prove its security.
Consider that we want to design another protocol: $P_2$ that uses $P_1$. Let's assume $P_2$ is a protocol that satisfies fairness property.
Question: Can we define $P_2$ using the simulation-based approach? Or it has to be game-based because $P_1$ is a game-based one.
Remark 1: By simulation-based approach, I do not mean necessarily mean UC.
Remark 2: It seems to me we can use the combination, as many crypto primitives like encryptions are game-based ones, but they are used in protocols defined using simulation model.


texts: Hash functions in XEdDSA and VXEdDSA Signature Schemes

texts:
Can someone please explain the below paragraph from section 2.5 in The XEdDSA and VXEdDSA Signature Schemes? Specifically I want to understand how we are defining the family of hash functions and how is it used further?

  XEdDSA and VXEdDSA require a cryptographic hash function. The default hash function is SHA-512.

  We define $hash$ as a function that applies the cryptographic hash to an input byte sequence, and returns an integer which is the output from the cryptographic hash parsed in little-endian form. Given $hash$ and the curve constants $p$ and $b$, we define a family of hash functions indexed by nonnegative integers $i$ such that $2^{|p|} - 1 - i > p$.

  ${hash}_i(X):\\
\;\;\text{ return }{hash}(2^b - 1 - i \;||\; X)$

  So $hash_0$ hashes $b/8$ bytes of $0xFF$ prior to the input byte sequence $X$, $hash_1$ changes the first byte to $0xFE$, $hash_2$ changes the first byte to $0xFD$, and so on.

  Different $hash_i$ will be used for different purposes, to provide cryptographic domain separation. Note that $hash_i$ will never call $hash$ with the first $b$ bits encoding a valid scalar or elliptic curve point, since the first $|p|$ bits encode an integer greater than $p$. Note also that $hash_0$ is reserved for use by other specifications, and is not used in this document.


texts: One-direction same size encryption algorithm that allows for partial replay

texts:
I am looking for a one-directional encryption algorithm that preserves the size of the input. Then I would like to be able to mix an encrypted with original data and to be able to receive the same result. It is probably hard to grasp, let me try to explain with an example: Let's say I have the input: This is some text to encrypt and the encrypted result with the same size says: xxxxxxxxxxxxxxxxxxxxxxxxxxxx. The algorithm should be able to calculate the same result from any input that mixes the original unencrypted bytes with the encrypted result: This is xxxx text to encrypt or This is some text xx xxxxxx. Note that providing a protocol that describes which area is the original and which is already encrypted is ok. It does not need it to determine this on its own.

An example use case that illustrates an application of such an algorithm: Alice and Bob play battleship. When Alice makes her choices, she encrypts them and sends them to Bob. Bob cannot make any sense of the data, else he will know where to attack. When bob plays his move, Alice reveals the field. Bob does not trust Alice that she did not change the order of the ships after he already told her his move - this is why Alice sends the board encrypted again with already stricken fields revealed. Bob now can apply the algorithm that can encrypt the revealed part to make sure that he will get the same result as the original send from Alice. NOTE: this is illustration use case - I am not looking for alternatives to solve this problem.

Can you give me ideas of algorithms that already provide this or something that I can base such thing on?


texts: Hardness of elliptic curve discrete logarithm problem?

texts:
I have just started to study Elliptic curve cryptography. I have a question: In elliptic curves in Fp (such as prime256v1 curve) I just learned that the discrete logarithm problem is, "finding k, where Q=kG and G and Q are known, is hard" (k is big integer and G is generator)

I'm curious if the below sentence is still correct?

"finding x or y or z is hard, where P0=xG, P1=xyG and P2=xyzG and P0, P1, P2 and G (also generator) are known"

I think there is too much information. Is this still hard?


texts:
We know that exposing $p$, or $q$ or $\phi(n)$ results in trivial attacks on RSA since they allow us to factor $n$ and to compute the private exponent $d$.

In OpenSSL (and most RSA implementations) decryption is done via the CRT, so we store $n$ and $d$, but also store $d \bmod (p-1)$ and $d \bmod (q-1)$ as CRT exponents.  Suppose these leaked... is there a practical attack?


texts: Why does dragonfly key exchange need hunting and pecking?

texts:
The dragonfly key exchange scheme (as used by WPA3) received criticism because the way it chooses a generator of the elliptic curve group ('hunting and pecking') is a non-constant time algorithm making it vulnerable to side-channel attacks.
My question is: Why is hunting and pecking used at all?
Assume there is a known generator $G$ for a group of prime size, then $G^P$ would also be a generator of the same group (if $P$ is not a multiple of the group size). With $P$ being a password-derived number (as with the dragonfly scheme as is), this way one would obtain a generator just as random and unpredictable as with hunting and pecking, no?
Where is the mistake in that reasoning?


texts: What is the difference between honest verifier zero knowledge and zero knowledge?

texts:
Zero-knowledge proof systems have three properties: soundness, completeness and zero-knowledge.
I can't understand the definition of "zero-knowledge".
What does "simulate" mean?
And what is the difference between "honest-verifier zero-knowledge" and "zero-knowledge"?


texts: Are there a way to progress or age key pairs

texts:
I am searching for a way to make the noise X pattern fully forward secret. The X pattern is a way to encrypted and authenticated messages. As a building block to achieve this I started pondering if there is a way to progress a key pair ($a$, $A$). Use a one way function on $a$ to calculate $a'$ and another function on $A$ to calculate $A'$ while $A'$ is the public key to $a'$. This process could the be repeated.
$\require{AMScd}$
\begin{CD}
    a @>>> a' @>>> a'' @>>> \\
    @VVV @VVV @VVV\\
    A @>>> A' @>>> A'' @>>>
\end{CD}
The idea is to house the progressing key pair in the receiving device and to burn old $a$:s at specific times. The sender could calculate the public key that is valid for a specific time (3 days from now) and then send.

Another way to achieve this would be to have a huge list of key pairs that expire at specific times. So this is a optimisation to get around using a huge list.

I am at this time more interested if this kind of functionality exist instead of if it is a good fit for my use case. Could it work with x25519 or ed25519? Could the function work so that $A$ could be progressed directly to $A''$ without calculating $A'$. Could it work some how with collective threshold decryption?

Update
Will not help in my case but just as an example. I believe that this kind of pattern could work. Probably broken for some reason...
$\require{AMScd}$
\begin{CD}
    a @>a^3 \: mod \: p>> a' @>a^{'3} \: mod \: p>> a'' @>a^{''3} \: mod \: p>>\\
    @VVa^5 \: mod \: pV @VVa^{'5} \: mod \: pV @VVa^{''5} \: mod \: pV\\
    A @>>A^3 \: mod \: p> A' @>>A^{'3} \: mod \: p> A'' @>>A^{''3} \: mod \: p>
\end{CD}


texts: What should the size of the private exponents in Diffie-Hellman key exchange for TLS be?

texts:
I'm using TLS with a Diffie-Hellman key exchange to negotiate the symmetric keys.
How long should the exponents be?


texts: Stream cipher example for an introductory cryptography course

texts:
I am looking for an easily defined stream cipher to illustrate two basic principles in an undergraduate cryptography course:

  not every bit of the internal state should be used in the keystream;
  some non-linear operations should be used to step the internal state.

So far, my only candidate is the Geffe generator. But this is a bit too easily broken. My ideal example would be a stream cipher showing (1) and (2) that was a bit stronger than the Geffe generator, but still easily defined, and still breakable by a correlation attack.

If there are no candidates then I'd welcome suggestions for a simple design meeting my requirements.


texts: How hard will it be to solve an equation in elliptic curve group/ cyclic group where Discrete Logarithm is hard?

texts:
Given an Elliptic curve group $E(\mathbb{F}_q)$ where the Discrete Logarithm Problem (DLP) is hard and a base point $G \in E(\mathbb{F}_q)$ with large prime order $n$, what will be the advantage of a polynomial-time bounded adversary $\mathcal{A}$ to solve the following problem:

Given $\alpha = X+Y$ and $\beta = X+Y+Z+r.a.G$, $\mathcal{A}$ should output the point $Z$.
$X,Y,Z \in E(\mathbb{F}_q)$, and $r,a \in \mathbb{Z}^*_n$. It is worth nothing that $r,a$ are sampled at random.

One can assume that $\beta$ is an encryption of the message $X+Y+Z$ using ElGamal Cryptosystem over Elliptic Curve.
P.S: I have the impression that this problem can be reduced to breaking the DLP problem, but I am not certain.


texts:
Let us assume the SubBytes operation changed to just shift right operation.
for example - f(00011101) = 10001110
How we perform a Known/ Chosen Plaintext Attack and find the key?
How much time does it take to find it?


texts: Why has the RSA factoring challenge been withdrawn?

texts:
Wikipedia states that RSA challenge has been withdrawn.

Does it mean that an efficient factoring algorithm is "just around the corner"?

or are there some other reasons?

If the challenge was still open people would have even more confidence in RSA.


texts: Formal definition of "explicit" algorithm?

texts:
A long time ago, I read that the definition of "cryptographic hash function" is "collision-resistant one-way function". (A similar definition shows up in the FIPS standards for SHA-1 etc.)

But this is not a sufficient property for many of the modern uses of cryptographic hash functions, like Bitcoin. What they really want is for hash functions to act like a "random oracle".

Of course, no deterministic function can be random.

I am taking Dan Boneh's Coursera cryptography class. Most cryptographic primitives we cover assume some sort of secret, and then the definition of "secure" involves probabilities over the space of possible secrets. For example, a secure RNG has a secret seed, and if I (a) pick a seed at random and generate a long pseudo-random string, and (b) pick a long truly random string, then no efficient algorithm should be able to tell them apart with noticeably better than even odds. (With those odds computed over the space of keys and truly random strings.)

In the intro lecture to hash functions (see here or here if you do not want to register), Boneh gives the following definition of "collision resistant" hash function:

  A function $H$ is collision resistant if for all (explicit) "effective"
  algorithms $A$, $$\mathrm{ADV}_\mathrm{CR}[A,H] = \mathrm{Pr}[A\ \mathrm{outputs\ a\ collision\ for\ } H]$$ is "negligible".

Now, obviously, a very simple algorithm exists to output a collision for, say, SHA-256; we just do not know what that algorithm is. And there is no indication in this definition of the space over which we are calculating the probability.

So my question is twofold:

What is the formal definition of "explicit" algorithm? (I assume this is meant to rule out algorithms that we know exist but cannot explicitly describe.)
Over what space is the probability being computed in Boneh's definition?

To clarify: I am aware of the dictionary definition of "explicit". I am asking for a formal definition. I know how to translate a statement like "There exists an algorithm such that..." into (say) the language of ZF set theory, at least in principle. I do not know how to translate "...but nobody knows what it is" into any formal language at all. So I am wondering how a mathematician would think about this sort of definition.


texts: Representing Ed25519 p curve in hexadecimal byte string

texts:
I am interested in representing p = 2^255 - 19 in the Ed255519 curve as hexadecimal byte representation.

When I was looking through the original NaCL source code written by DJB, I saw a code fragment that says:

static const unsigned int minusp[32] = {
 19, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 128
} ;

Am I safe to assume that this is the 32 byte integer representation of p = 2^255 - 19  and all I need to do is translate the 32 byte integers into 32 byte hexadecimal string representation ?

How should I represent the p for Ed25519 in hexadecimal string ?


texts: How to verify CA certificate from Yubico with openssl?

texts:
I'm going to verify the CA certificate from Yubico. I copied the whole certificate from

-----BEGIN CERTIFICATE----- to  -----END CERTIFICATE----- in a file with the ending .pem. Then I wanted to verify this with openssl verify test.pem in the command line (test.pem is my file with the certificate). I got

test.pem: CN = Yubico U2F Root CA Serial 457200631
error 18 at 0 depth lookup:self signed certificate
OK

I'm very new to openssl and openSUSE, so I don't know how I can solve this problem. My aim is to verify a certificate against this CA file. But first I want to get this error off.


texts: What's the safest way to encrypt a messenger application?

texts:
How can I safely encrypt a messenger application that sends data over the Internet via TCP?

I've already taken a look at Salsa20, but I don't know if that's a good algorithm to use for this.

What algorithms can I use for this and how secure are they?


texts: Is there a administrator key that can decrypt all ciphertexts encrypted with different keys by different persons in a group?

texts:
here is the scenario:

$A, B, C, \ldots, Z$ are in a group with a administrator $Admin$,
each of the users in the group has his own key $Key_A, Key_B$, and so on...
everyone encrypt his own information with his own key,

but would it be possible to have a key such as the Admin would have the possibility to decrypt all the ciphertexts of all the users?

  I had a simple idea:

  the Admin share a master key with all the members in the group,
  all users register his identity at the Admin,
  the Admin generate every user's secret key for every user,
  the Admin share keys with all the users.

  but in this way the Admin will know all the users' keys, this is insecure.


texts:
Wikipedia has a nice section regarding the speedup of the RSA decryption using the Chinese Remainder Theorem here. I need to understand the implementation of a similar speedup for the encryption algorithm of a more complex homomorphic encryption scheme (DGK) and, for some reason, I'm unable to get my head around the way the Chinese Remainder Theorem is used to achieve this. I don't have a lot of background on modular arithmetic and I would really appreciate it if someone could explain this in more detail.

Edit: Following @mikeazo's comment, I just want to understand the way CRT is applied to speed up the RSA encryption.


texts:
I am following the Coursera Cryptography I course and I have the following question,

I am a bit perplexed by the statement, in week 2 lecture "What are block cyphers?" that a counter-mode PRF is a secure PRG.

PRPs are PRFs, and PRPs have the property that if (x₁, x₂) ∈ X, x₁ ≠ x₂, then PRP(x₁) ≠ PRP(x₂) -- since they are invertible.

Using a PRP in counter mode results in a series of values which are all different from each other. Now -- this is not random. In fact, we can see that, in the case of a 128 bit PRP, for example, after 2⁶⁴ different output it is actually more likely to get a repeat than not. However the PRG we created won't have this behavior and we would be able to distinguish them.

In other word, wouldn't this PRG susceptible to a birthday attack?


texts: Generate a new public/private key pair for each new message?

texts:
When using PGP type public encrypted communication, would it be a good idea to generate a new
public for each message and attach that in the new public key in the reply to back to sender mail body? Idea is you start the communication with the known public key from a key server, but for each new message/chat message you generate a new public/private key for that particular end-user. That way if someone cracks your initial public/private key they may not read all the messages? Would that be a good or bad idea? Ie the person who want to read your mail conversation must crack all PGP keys in the conversation sequence to read all the messages.


texts: Approach used with XOR cipher in black box scenery

texts: What's the approach used in cryptanalysis to make an decrypter for a simple xor stream cipher in a Black Box scenery with only the output?


texts: Explaining the reason of radically more accuracy while using different set of hash functions instead of same set of hash functions on some operations

texts:
So I am looking for an explanation of an experiment.
In this experiment, I took a set of k hash functions. Say the total number of data points I am working on is d. Call an algorithm A which used that set of hash functions to do some operations on d data points and have modified them to a matrix B.It is mentionable that algorithm A introduces a bunch of randomization. So applying algorithm A different times with same set of hash functions and same set of data points will produce different results. Now we apply algorithm C on that matrix B and get a result, call it D.
So this is the summary of what I am trying to do in short.
Now I can do this multiple times in two ways-

I take a set of k hash functions in the beginning. Now I run algorithm A with the same
set of hash functions and on the same set of data points n times and produced n different matrixes and averaged the respective elements of those matrixes to produce a final matrix, call B'. So in short, the (i,j)th entry of the matrix B' is the average of (i,j)th entry of n matrixes we got before. Now , we run algorithm C on matrix B' and get a result D
I take a set of k hash functions, run algorithm A, generate matrix B and then run algorithm C on matrix B to produce result D. Now, I run this process multiple times, every time with a different set of hash functions and then average all such Ds and produce D'
Interestingly, process 2 gives just radically more accurate results and I don't know how to explain this behavior. One thing to mention, I was using sha256 in this experiment.
I hope to get help from kind people out here in order to solve this.
Thanks in advance!
Edit: This has been used for some differential privacy operations and the results accuracy is being measured by comparing with the ground truth
Edit2: By indicating that I used k different sha256 hash functions, I meant that I just generated k seeds and appended them before the string I am tryna hash, for example,

hex_num = hashlib.sha256((str(seed[i])+str(d)).encode('utf-8')).hexdigest()

Hope it is clear now


texts: In many cryptographic protocols, some information is transmitted within smart cards. So, what is a smart card? Is it a physical card? What are they used for in cryptographic protocols?