Can I use different IVs when encrypting identical plaintexts with identical keys with AES-CTR? I would like to use AES-CTR to encrypt the same plaintext with the same key more than once (on different machines). I'm wondering whether I should try to use the same IV each time, or whether it's safe to use a random IV for different instances of the same plaintext. Using the same IV would require a deterministic method for IV selection, which poses its own problems.
I've seen very good explanations of why one shouldn't re-use a key/IV pair when encrypting different plaintexts using AES in CTR mode. (https://crypto.stackexchange.com/a/2993/83956)
I'm wondering whether encrypting the same plaintext twice with the same key but a different IV opens you to a similar attack. As I understand it, this would provide an attacker with
$C_1 = P \oplus F(K, IV_1)$
$C_2 = P \oplus F(K, IV_2)$
...which means:
$C_1 \oplus C_2 = F(K, IV_1) \oplus F(K, IV_2)$
...which doesn't look useful to me, but that depends on $F$ which I'm not familiar with.
Context: I have a system which requires a password and secret key together in order to log in. In a web client, I would like to save the secret key in local storage for convenience. I understand it is bad practice to leave secrets unencrypted in local storage, so I'm encrypting it with AES-CTR using a key generated from the user's password. The encrypted key will never be transmitted—only decrypted using the password for login purposes. They key is compressed before encryption, so any guesses at the password cannot be validated by attempting to decrypt the secret key. All guesses produce valid-looking secret keys, so an attacker would still have to use actual login attempts to brute force anything.

I'm wondering whether I should try to use the same IV each time,

No. Using the same IV twice for the same message means that you leak that you sent the same message. If your set of messages is somewhat small this allows an adversary to more easily correlate reactions to messages with possible message contents.

whether it's safe to use a random IV for different instances of the same plaintext.

Yes, it is. The security definition which CTR satisfies (CPA security) very much considers the fact that the same message is sent twice. This will not leak anything (within reasonable bounds). To see this note that $F$ is usually modelled as a PRF, that is if your adversary doesn't know the key it might as well be a truly random function $f$ which takes its input, draws a response uniformly at random and stores the mapping for this input. This means that $F(K,I_1)$ can be translated to $f(I_1)$ which can be translated to the random string $R_1$ and the same can be done to construct $R_2$. Then if you look at $C_1=P\oplus R_1$ and $C_2=P\oplus R_2$ you will notice that both are "essentially encrypted with the one-time-pad", i.e. independent and uniformly random keys of size equal to the message length which will obviously not leak any information.


Why I can get a key from frequency in Caesar Cipher? I took a cryptanalysis class in university and I learned Caesar Cipher. But I cannot understand why frequency gives me the "key".

In a meterial, the following sentences are explained:

  When Eve tabulates the frequency of letters in this ciphertext, she
  gets: I=14, V=13, S=12, and so on. The most common character is I with
  14 occurrences. This means key = 4.

What I cannot understand is the last sentence, "This means key = 4". Most frequency alphabet is "E" which has 12.7 frequency and the number of "E" is 4 I know. But how can I compute it from the frequency? I want to totally understand this mechanism.

This will make it more clear:

A B C D E F G H I J ...
0 1 2 3 4 5 6 7 8 9 ...

The Caesar cipher starts with the letter and goes through the alphabet using the key, wrapping around after 'Z'. So if 'I' is the most common letter then this is probably the enciphered letter 'E'. And since index('I') - index('E') = 8 - 4 = 4, that's the key that was used.

Note that E is only the most common letter for English text and only if other characters like space are not counted. It may not be the most common letter in small ciphertext.


Java RSA Padding: no libraries used I'm trying to implement RSA without using any java libraries using the algorithm from wikipedia HERE

So, anyone can clearly see that it is a raw RSA, and can directly be attacked.

The question is how can i include padding to the algorithm because i'm not using Java libraries, so what is the simple algorithm to implement the RSA padding to make it secure against some attacks?

Also, would Padding alone be enough? or there is something else i need to know?

Any help is appreciated.
Thank you.

Do not use raw RSA at all.

First simple attack starts when (plain ^ public_exponent) < n , i.e. when the message to be encrypted is small. Then there are more sophisticated attacks and forgeries as soon as 1 plain text and the corresponding cipher text are known, or even can be guessed. And then you have to review all possible attacks on RSA for the last 30+ years. No way.

Implement padding pkcs#1 named RSA-OAEP (based on MGF function, a variant of a feistel cipher).


When homomorphic encryption goes wrong? Consider I have two ciphertext $c_1$ and $c_2$ encrypted using RSA encryption. By definition if I multiply them I'd get $c_1.c_2 \ modN$. My question is what would happen if $c_1.c_2 >N$. Can we still decrypt it and obtain the product of two plaintext?

Yes; as long as the product of the two plaintexts $p_1 \cdot p_2 < N$, you'll get their product; it doesn't matter what the ciphertext values actually are.

The relevant question is: what happens if the plaintexts overflow; that is, what if $p_1 \cdot p_2 \ge N$?  In that case, when you decrypt, you'll get the result $p_1 \cdot p_2 \bmod N$


Is it secure to transmit a short plaintext with its MAC? I have a short (32-bit) message that needs to be authenticated.  Due to the constraints of my platform, I would like to use Speck32/64 (32-bit block, 64-bit key) with a Matyas-Meyer-Oseas one-way compression function (due to its ease of implementation and because the input sizes match what Speck generates).

(Here, $E$ is Speck32/64, $g$ is a no-op, $m_i$ is the entire short message, $H_i$ is the tag, and $H_{i-1}=H_0$ is secret.)

However, my message is short enough that there won't be more than one iteration of the compression function; essentially, I would merely be XORing the output of the cipher with the plaintext.  (Obviously, $H_0$ should remain secret!)  I also don't care about the secrecy of the message, only its unforgability.  Therefore, I would transmit the message in plaintext along with its equally-sized MAC.

Is it secure to give a third party the plain text that goes with a MAC?  In other words, does the fact that the third party always knows the plaintext to a given tag weaken the security of the tag?  If so, what needs to be changed to secure the message?

A normal security notion for MAC's is that of unforgeability. So given some set of message,tag pairs $(m_0,t_0),\ldots,(m_k,t_k)$ is should be hard to create a tag for a new message not among the $\{m_0,\ldots,m_k\}$, stated informally.

In your case, you could just use $E_k(m_0)$ with the secret MAC key $k$ ($H_0$ in your notation); no need for the extra XOR (it does nothing for security; you know $m_0$ anyway, so we might as well use $E_k(m_0)$). This is just a standard use of a keyed random function (which we will suppose a block cipher is) as a MAC for short messages. It's construction 4.5 on page 117 in Katz and Lindell (second edition) book "an introduction to modern cryptography", which also has the (short) security proof for this construction for the above notion of security.

You do realise that your construction does allow for replay attacks, I suppose?


How to securely store data? / How to securely encrypt a file? How do I safely encrypt a file?

or formulated differentely:

How do I safely store the data of my application in a file?

Note: Using established tools isn't an option for this. The tasks need to be done at program level (using libraries and such).

Ask yourself if you even can securely store the user's data.
This includes to check that the user won't get sniffed by the root / admin
user.Also make sure that your implementation is secure.Employ
standard code review mechanisms, make sure that your implementation has
countermeasures against timing attacks (like against AES).Also make sure
that you use appropriate data types.Using a byte* allocated using malloc
usually isn't very secure. If your library provides mechanism for data
storage, use them! Your OS may also provide means to protect data
while in memory, for example the data protection API in Windows only relies
on the current user and can be used to conceal sensible keys in memory.
Reading Schneier's Cryptography Engineering may be a very good idea for you,
to ensure you don't have side-channel leaks.
Ask yourself what you can use to authenticate the user. The
options are (it is explicitely allowed and recommended to combine as
many of them as convenience and availability allow):

Passwords: Your user can supply a password or a passphrase. Do
not limit him in length of this, to allow him to use good and long
passphrases. This usually is a good choice, as it requires the user to know
something and this hence can not be lost like an usb-stick.
Keyfiles: Allow the user to provide keyfiles. These files may
look arbitrary, but should be rare. Allow the user to use the
(cryptographical) random number generator of your application to generate
strong keyfiles (of 64 bytes length or more). Examples for keyfiles are rare documents, like personal (word/) text documents or on-purpose generated files just containing random data (created using the application's random number generator).
Custom Hardware: If you are deploying in large scale you can force
the user to be required to use a tamper-resistand hardware device. This
device should support symmetric encryption with a device-held key.
User's Hardware: Allow the user to use his PKCS#11 or similar
smartcard or cryptographic token, which provides public key encryption, to
be used. Also allow the user to protect the key using the TPM (if
available)
OS data: Allow the user to make the decryption dependant on
something stored in the current OS, like the user credentials or OS
provided secure key storage.

Inspect what algorithms you have at your disposal. You'll need (at
worst) five classes of algorithms: Password-based key derivation functions,
encryption algorithms, modes of operation, message authentication codes and
cryptographically secure random number generators.At the time of
writing the following algorithms are recommended (in descending order). If
functionality is already provided more top-level don't use it.

Cryptographically secure random number generators:

Fortuna
An approved algorithm. This may either be the result of a
contest or some approved algorithm by some trusted institute (e.g. ANSSI,
NIST, BSI, ...). Avoid algorithms with "provable" security where the
institute provides the parameters, these parameters may be chosen on
purpose to get back-door access. For seeding use the cryptographically
secure random number generator of your OS. They are usually a bit
hidden.
Some "weak" standard approach. (i.e. run a blockcipher in CTR
mode and delete key and IV as soon as possible) Get the key and the IV
from the cryptographically secure random number generator of your OS.
They are usually a bit hidden.

Password based key derivation functions:

The winner of the PHC-competition. If there are multiple
winners, ask for the differences and use the one most suited for your needs.
scrypt
bcrypt
PBKDF2, using an efficient and secure hash function (on your
platform)
implement your own PBKDF2!

Ciphers:

The winner of the CAESAR-competition (2018+). If there are
multiple winners, ask for the differences and choose the appropriate one.
AES. Note: For data that needs to be confidential unti 2070 or
earlier, it is recommeded to use AES-128. In every else case use AES-192 or
AES-256.
ChaCha(preferred) or Salsa20.
One of the following three: Threefish, Serpent or Twofish
3DES with 3 keys. (needs 168 bits of keying material)

Modes of operation (this is obsolete for CAESAR-winners):

OCB (If the patent has expired)
GCM
EAX (preferred) or CCM
CTR, below this a message authentication code is required
(including)
One of the following: CFB or OFB
ECB, avoid at all cost, rather implement your own CTR!

Message authentication codes:

Poly-1305 using a standardized construction
HMAC, using a secure standardized hash function, preferably
SHA-3 or a member of the SHA-2 family. Encrypt the data first,
then authenticate the ciphertext!
implement your own HMAC!

Ask yourself on how to design the header. The header should contain:

The salt, a random 64 byte or more value that will be newly
chosen on each single creation of a new file. This will be fed into the
password-based key derivation function. The salt can be open, but may be
authenticated using the authentication mechanism.
The parameters for the password-based key derivation function.
These parameters need to be open. They should be chosen such that key
derivation needs approximiately 100ms to 1s on the target platform. A
value indicating the password based key derivation function used is
considered a parameter.
A nonce or an IV for the cipher / mode. This value should be chosen
at random and be stored openly.
The remainder of the header should be encrypted and
authenticated.The before-mentioned nonce/IV should be used along with
the key derived from the password using the password-based key derivation
function and the stored salt and parameters.
The master-keys for the data part of the file. These should be
random and maximal length. This is part of the encrypted part of the
header
A nonce / IV for the data part. This value should be random. This
value can (and should) be part of the encrypted part of the header.

The actual data is now encrypted using the above chosen
cipher/mode/authentication triple and the key/IV/nonce pair of the encrypted
part of the header.

Now some question that may arise:

Is it worth it to use multiple-encryption?No.The benefit
by double encryption is only 1-bit due to the meet-in-the-middle attack.
Streamciphers may be combined easier, but it is absolutely unneccessary as
all ciphers are unbreakable for the forseeable future (50 years+)
What authentication methods should I use?As many as possible,
but at least passwordYou need to have a very good reason not to use
passwords because everything else can be attacked with admin rights or can
be stolen.
You didn't mention the other four authentication methods in the header
part, how should I incorporate them?

Keyfiles: Assume that each keyfile has low entropy. That being
said, you can't really do alot against it. Derive a key from every keyfile
using some digest-expansion function and your favorite secure hash function
(SHA-2/3) and construct a big XOR consisting of all file's hashes and the
user's password. This would look like this: $Key = PBKDF(PW) \oplus H
(File_1) \oplus H(File_2) \oplus ...$, where $\oplus$ denotes bitwise XOR.
Custom Hardware: At the creation of the file let the device
generate a symmetric key that will be kept inside the device. Perform
everything up to the keyfile / password level (see directly above point) and
then send this to the device for encryption. The key being used doesn't have
to be unique for each file. It is suggest that one key is being used for all
files. It is also possible to add an identifier to the file to identify the
associated hardware key.
User's Hardware: Let the device generate an OpenPGP key or a valid
S/MIME encryption certificate. Send the key being the result of the step
directly above (or 2 steps above) to the device for decryption. It will
decrypt it and return the key used to decrypt the master-keys.
OS data: If you have user credentials (maybe some random strings),
hash them and incorporate them at the same time in the same way as the
keyfiles. If your OS provides you secure storage (or your TPM does), store a
key and pass it in as "keyfile", thus hash it and incorporate it in the XOR
step.

Should I use an open source library or some closed-source library?Open-SourceChances are very good that there aren't any security
issues in well-known open-source libraries, whereas closed source puts
restriction in regard of when you can use it, usually you have to pay to be
able to use and you can't usually inspect the code on your own to make sure
it's secure.
Why did you use XOR to include keyfiles?(relates to question 3)Convenience.If
you don't use something that is commutative, like XOR, users will run into
problem because files have to be supplied in the exact same order. This gets
even harder if files are just re-named but their contents are kept. And from
a security perspective this is no less secure as one basically constructs a
"stream cipher" with the password based key derivation function output, the
hashes of the keyfiles and the other outputs (TPM, credentials,...) which is secure as
long as one source is secure.


Where can i find relative software for differential cryptanalysis? Is there any publicly known software for differential cryptanalysis over some cryptographic building blocks as blocks ciphers or cryptographic hash functions

Not to my knowledge. Here is a possible explanation: non-trivial differential attacks are rather difficult to find in a fully automated way, and most of the time, one requires some (human) insight from a cryptanalyst before beginning to write some software.

Another explanation could be the following: cutting-edge differential attacks (like against SHA-3 candidates, for instance) are performed by world-class crypto researchers, and the competition (being the first to publish) is rather rough. So, people do not take the time, or are not always willing to share their software with everybody.


Why is an Encrypt-and-MAC scheme with deterministic MAC not IND-CPA secure? I'm preparing myself to exam, but I have a lot of troubles with rigorous proofs. It's the task from two-years ago exam. At the bottom I reminded one definition.

  Let $(Gen_E,Enc,Dec)$ be an IND-CPA-secure encryption scheme.

  Let $(Gen_M,Mac,Vrfy)$ be a secure MAC.

  Define an encryption scheme as follows:

  $Gen'$ upon input $1^n$, generates $k_1 \leftarrow Gen_E(1^n), k_2 \leftarrow Gen_M(1^n)$,
  $Enc'$ upon input key $(k_1,k_2)$ and message $m \in \lbrace 0,1 \rbrace^*$, computes $c=Enc_{k_1}(m)$ and $t=Mac_{k_2}(m)$ and outputs $(c,t)$.
  $Dec'$ upon input key $(k_1,k_2)$ and ciphertext $(c,t)$, outputs $Dec_{k_1}(c)$ if $Vrfy_{k_2}\left( Dec_{k_1}(c),t \right)=1$ and outputs $\perp \not\in \mathcal{M}_n$ otherwise.

  Prove that this construction is not even IND-CPA-secure when the Mac algorithm is deterministic.

Reminder (IND-CPA-secure).

  An (efficient secret-key) encryption scheme $(Gen,Enc,Dec)$ is IND-CPA-secure if for any PPT adversary $\mathcal{A}$ it holds that $Pr[PrivK^{cpa}_{\mathcal{A}}(n)=1]-1/2$ is negligible function, where $PrivK^{cpa}_{\mathcal{A}}(n)$ denotes the output of the following experiment:

  (a) Let $k \leftarrow Gen(1^n)$

  (b) The adversary $\mathcal{A}$ is given input $1^n$ and oracle access to $Enc_k(\cdot)$. It outputs a pair of messages $m_0, m_1 \in \mathcal{M}_n$ of the same length.

  (c) Let $b \in \lbrace 0,1 \rbrace$ be chosen uniformly at random. Then a ciphertext $c \leftarrow Enc_k(m_b)$ is computed and given to $\mathcal{A}$.

  (d) $\mathcal{A}$ is given the challenge ciphertext $c$ and oracle access to $Enc_k(\cdot)$. It outputs a bit $b'$.

  (e) The output of the experiment is $1$ if $b'=b$, and $0$ otherwise.

If you could help me with the rigorous proof, I'd be really grateful for your time.

I'm a little bit confused by your notation (what's $1^n$ supposed to mean? based on context, it looks like a key or a passphrase, but I've never seen that notation before), but the exercise itself seems to just amount to proving that an Encrypt-and-MAC scheme, using a deterministic MAC of the plaintext which is sent in plain, cannot be IND-CPA secure.

To prove that, keep in mind that there's nothing in the IND-CPA definition saying that the adversary cannot use the encryption oracle on the challenge messages.  Since the MAC is deterministic and sent in plain, the adversary can just compare the MAC parts of two encrypted messages to determine (with very high probability) whether they encode the same plaintext.


RSA Encryption problem for Discrete Math I am doing practice problems for my upcoming final exam, and am having trouble with this RSA encryption problem. If any one could check to see if i did these correctly, it would be greatly appreciated.

For (a) I got $\mathbb{Z}^*_8 = \{1,2,3,4,5,6,7\}$,

(b) i got $3*3 = 1 \text{ mod } 8 = 3^{-1} = 3$

(c) this one i am not sure how to do

(d) $M = N^d \text{ mod } 15$, i got $d = 3$, so $M = 4^3 \text{ mod } 15 = 4$


The interaction between the malicious Adversary and the Simulator and Real-Ideal' views This example is from “Efficient Secure Two-Party Protocols-Carmit Hazay-Yehuda Lindell”.

And the security proof of the above example is this:

I have drawn a picture that is deduced from the above security proof.

Picture1:

[

Picture 2:

I have several questions:

Please, explain to me how the simulator and the adversary interact with each other? I mean what kind of requests can the simulator send to the adversary and vice versa. (what kind of requests can the adversary send to the simulator).
According to the security proof and the picture 1, why does the simulator get input x from the adversary and not from corrupted P1?
Should simulator trust the adversary? I mean is it possible that the adversary, in picture 1, modifies input x, deliberately, and then give it to the simulator? If yes, how will the simulator figure out this modification?
Would you please explain to me what is the real view for P1 and P2 in both pictures? Please explain to me what must the simulator simulate in picture 1 and picture 2?

Page 24:

According to the above definition 2.3.1 and the description on page 24, I think the answer is like this:

Case1: When P1 is corrupted: real view of P1 is (x) and real view of P2 is (x, y, x ^ y)
And simulator must simulate P1’s view and P2’s output.

Case2: When P2 is corrupted: real view of P1 is (x) and real view of P2 is (x, y, x ^ y)
And simulator must simulate P2’s view and P1’s output.

If my answers are not correct, please correct them.

Without meaning any offense to the authors, this proof could perhaps have been written a bit more clearly; probably, since this is a fairly minor result, they didn't expend too much effort on it. Here is a longer but hopefully clearer rewording which should clear your terminological confusion.

Corrupted $P_1$

The real-world adversary $\mathcal A$ corrupting $P_1$ has input $x$ and auxiliary input $z$. It sends some value $x'$ to $P_2$ and outputs some value $x''$; both $x'$ and $x''$ are computed from $x$ and $z$. Since $P_2$ is honest, it computes and outputs $x' \wedge y$, for its received value $x'$ and input $y$, as instructed by the protocol; the output pair is $(x'', x' \wedge y)$.

The ideal-world adversary $\mathcal S$ (aka the simulator) again has input $x$ and auxiliary input $z$; it first computes $x'$ and $x''$ from $x$ and $z$ just like $\mathcal A$ does*. It then sends (or instructs $P_1$ to send) $x'$ to the trusted party; the honest $P_2$ sends $y$. The trusted party returns $\varepsilon$ (the empty string) to $\mathcal S$ and $x' \wedge y$ to $P_2$. $\mathcal S$ outputs $x''$ and $P_2$ outputs $x' \wedge y$; the simulation is perfect.

Corrupted $P_2$

The real-world adversary $\mathcal A$ corrupting $P_2$ has input $y$ and auxiliary input $z$. It receives $P_1$'s input $x$ and outputs some value $y'$ computed from $x$, $y$ and $z$. Since $P_1$ is honest, it outputs $\varepsilon$ as instructed by the protocol; the output pair is $(\varepsilon, y')$.

The simulator $\mathcal S$ again has input $y$ and auxiliary input $z$; it sends $1$ to the trusted party, and the honest $P_1$ sends $x$. The trusted party returns $\varepsilon$ to $P_1$ and $x \wedge 1 = x$ to $\mathcal S$. The honest $P_1$ outputs $\varepsilon$, and $\mathcal S$ computes and outputs $y'$ just like $\mathcal A$ does; the simulation is perfect.

* This is basically what they mean by "$\mathcal S$ receives [...] from $\mathcal A$." You could consider that $\mathcal S$ is given black-box or oracle access to $\mathcal A$: it sends $\mathcal A$ the values $x$ and $z$ and $\mathcal A$ returns $x'$ and $x''$ like it does in the real world. It's a bit awkward, however, because such black-box/oracle access has not been defined at this point in the book, and in particular does not appear in the security definitions.


Garbling in the wild (soft question) I am curious to know whether (Yao's) garbled circuits are actually deployed in practice. There has a lot of works on optimising garbled circuits (e.g., here and here) and I am interested in whether these simply of theoretical interest or with practical applications in mind. (A quick Google search did not yield much.)

Bolt labs uses Garbled circuits (from emp-toolkit) for channel management between the merchant and the customer. More on their blog post
In general, I don't think Garbled circuits is one of the most efficient MPC protocol out there for most tasks. So you're not likely to find many practical applications.


Entropy of two concatenated random values In this Intel blog posting, the author claims:

  The amount of work required to brute-force predict a random value that has n bits of entropy is $O(2^n)$. If you concatenate two values together, the entropy required to brute force the result becomes only $2^n + 2^n = 2^{n+1}$. By combining two n-bit random values, each with n bits of entropy, in this manner you get a random number with effectively only one additional bit of entropy.

Is this correct? My intuition suggests it would be $2n$ bits of entropy. But on the other hand, the two values are independent, so I can kind of see why it might be $n+1$ bits. Can anyone explain this?

Even in context, much of what is written in the blog post makes no sense. E.g., it says:

  While it can be argued that the DRNG is in reality just splitting a 128-bit value into two pieces and handing them to you one piece at a time, from a theoretical viewpoint this does not matter. While the original value had 128 bits of entropy, the end result is that you are handed two 64-bit numbers one at a time, each of which only has 64 bits of entropy. Because they come from a pseudorandom number generator, the entropy is additive when the values are concatenated, and the resulting 128-bit number has only 65 bits of entropy.

This is just wrong. If you have a 128-bit string that's truly uniform (i.e., has 128 bits of entropy) and split it in half then concatenate the halves, you clearly still have the original string and thus 128 bits of entropy.  The rest of the post is a similar muddle, so I wouldn't give it much credence.

Entropy of independent random strings is indeed additive, but not in the way the post says. Concatenating independent strings having entropy $n$, $m$ yields a string of entropy $n+m$, full stop.

Note however that the strings need to be truly independent to reach this conclusion. Strings generated as outputs of a deterministic RNG algorithm will not be truly independent, and in fact their concatenation will not have any more true entropy than that of the seed provided to the RNG (and may even have less).

I don't know whether the outputs of these Intel instructions can be considered independent or not, but either way this aspect of the blog post is incorrect.


How do i generate the shared key from this question? Say I have Alice and Bob:

Alice has $XA$, $YA = g^{XA} \bmod P$, $RA$ (random number)

Bob has $XB$, $YB = g^{XB} \bmod P$, $RB$ (random number)

Assume they have exchanged their certificates and they perform the following exchange.

\begin{align}
A\to B&:y_B^{RA}\\
B\to A&:y_A^{RB}
\end{align}

The shared key is  $Z_{AB}=g^{RA+RB}$

I am trying to make sense of how they will be able to come to the shared key.

If I am bob I derive the key by:

$(YB^{RA})^{XB^{-1}} = ({g^{XB}}^{RA})^{XB^{-1}} = g^{RA}$

The I issue I am facing is the ${g^{XB}}^{RA}$ is actually ${g^{XB}}^{RA} \bmod P$ so how do I remove the $XB$ from  $({g^{XB}}^{RA} \bmod P)$ to get $g^{RA}$

EDIT:

To make it more clear using numbers:

Say: $XB =4 ,g=9,P =23,RA=6$

Alice sends bob:
\begin{align}
A\to B:&y_B^{RA}\\
&y_B^{RA} \bmod P = 16^{6} \bmod 23 =12 \\
\end{align}

How would bob extract the $RA$ from 12???

Bob can try:

$(YB)^{RA\cdot XB^{-1}} = (16)^{RA \cdot 1/4} mod 23$

As can be seen above how i extract the value of RA?? in terms of $g^{RA}$ and there has to be only one answer if not how would bob know the which answer alice is using? Does it matter which answer alice is using?

First note that by basic power laws:

$$(a^b)^c=a^{b\cdot c}$$

and then note that this here is simply an application of that:

$$\left(y_B^{RA}\right)^{XB^{-1}}=\left(\left(g^{XB}\right)^{RA}\right)^{XB^{-1}}=\left(g^{XB\cdot RA}\right)^{XB^{-1}}=g^{XB\cdot RA\cdot XB^{-1}}=g^{RA}$$

where all equalities hold in all multiplicatively written groups (actually in all monoids), such as $\mathbb Z_P^*$ and $XB^{-1}$ is computed modulo the group's order, e.g. $\varphi(P)$ for $\mathbb Z^*_P$

As for your numerical example, with $g=9, RA=6, XB=4, P=23$, first note that the multiplicative order of $g$ is $11$, which means we need to calculcate $XB^{-1}\bmod 11=3$ and then everything just works:

$$g^{RA}=9^6\bmod 23=3=12^3\bmod 23=(y_B^{RA})^{XB^{-1}}$$

And of course you probably also want to note that $$Z_{AB}=g^{RA+RB}=g^{RA}\cdot g^{RB}$$, so you don't actually need to recover $RA$ nor $RB$ but only $g^{RA}$ and $g^{RB}$, one of which either party can compute directly and the other using the above formulas.

If you want to carry out these computations with realistic numbers yourself, you normally use the little Fermat or the EEA for finding the multiplicative inverses, using also e.g. repeated-square-and-multiply. Finding the order of $g$ can be a bit tricky at times, because you only know that it must divide the group order (by Lagrange's theorem), so you could just pick a safe prime and use a $g$ that has order $q$ for $p=2q+1$ with $p,q$ prime. Finding such an element is quite straightforward in that you check increasing candidate values until you get one that matches the following three conditions:
\begin{align}
g^1\neq 1\\
g^2\neq 1\\
g^q=1
\end{align}


Is it possible to determine the number of characters used for a password used to encrypt a file with AES 128? I lost a password for an ethereum wallet at the end of 2016. Computer immediately shutdown and password was not recoverable.

I know there are many potential avenues for narrowing my search for what my password could have been, but I am wondering if the number of characters can be determined from the encrypted file?

I dont know if this would make a difference but it was an ethereum wallet, using Geth

No. Password cannot be used to encrypt anything directly unless it is exactly of a certain size, and then it will be likely weak. Encryption passwords are hashed, with a slow hash hopefully, and the output is used as key.


Would a pictographic, phoneme-based, hand cipher be difficult to crack with computer crypt-analysis? What I'm talking about is a hand cipher which uses phonemes instead of individual characters and pictograms instead of the usual shuffling/substitution methods (e.g Caesar, Solitare, Vignere).

The pictograms would be composite images made from smaller images that represent each phoneme in the word. These images are are drawn by hand.

Would this deter computers at all in breaking the cipher? (I'm thinking it would be difficult to input the images for analysis given our current image recognition utilities).

Yes, of course it would deter computers...

... if it were done as substitution and every instantiation of a symbol had a new meaning. This would avoid frequency analysis.

But you are going to be drawing a lot of pictures, and your correspondent is going to need a thick book of hand-drawn symbols if you have a lot of traffic (will each of your hand-drawn symbols look exactly alike each time you draw it?).

Moreover, you now have a physical security problem. And keep in mind that this isn't art class--it's cryptography. But what you propose was widely done in the past, especially in the sixteenth century, and it was serious business.

However, the sixteenth century is over.

If you go ahead anyway, you should not reuse your symbols if they map one-to-one to an individual phoneme (if you only use substitution and not transposition). If you are ambitious and you enjoy drawing, you could create a system in which you map a phoneme to a different pictogram each time, which would surely be effective--but, again, this would all be time-consuming.

Nothing is gained by using phonemes, and perhaps nothing is gained by drawing the symbols by hand (unless you do not trust your computer).  Just use ASCII or extended ASCII.

Let's skip the fact that not only will the language have to be agreed upon, but also the dialect. Doing this for English (at least) is going to become a rat's nest of uncertainty very quickly. Which system of phonemes to use also needs to be determined, and this will not be easy. Will you use IPA?  Will you say there are 42 or 44 phonemes? Which English dictionary will you use to determine/check the pronunciation?  What is the pronunciation? If you look at various English dictionaries, you might be surprised to discover that they sometimes disagree about proper pronunciation.

Anyway, let's consider this ciphertext (plaintext "go up") based on English phonemes:

  β ┤ Ω ♯

Is a computer going to be able to break it without knowledge of your code book?  No.  Without knowledge of your preshared secrets, cryptanalysis is going to hit a wall.

Is this cryptography?  Yes. According to Claude Shannon:

  ... “true” secrecy systems where the meaning of the message is
  concealed by cipher, code, etc., although its existence is not hidden,
  and the enemy is assumed to have any special equipment necessary to
  intercept and record the transmitted signal.

But do we want to go back to this the kind of primitive cryptography? Other methods exist which are much easier and far better--and may offer an integrity check and authentication.


Are formal methods used for cryptographic protocol design? I decided to learn more about the application of formal methods to cryptographic protocols and found this interesting talk by Cathy Meadows at YouTube.

After doing research about how people are using formal methods, it seems to me that they're not being used for design. In other words, formal methods are being applied by researchers to cryptographic protocols that were already designed and published by organizations.

Why are those organizations not applying those same formal methods while they're designing the protocol? Why don’t those organizations seem to care about formal methods in the first place? Is there a disagreement between academia and industry about the usefulness of those tools?

In my experience the persons doing the standardization may not know about formal methods in the first place. And even if a formal method was used, they would not know how to assess it.

Note that whatever mathematical method is applied, the security of a protocol is still dependent on how the domain was modelled. If the model is even slightly incorrect, a protocol may still be insecure. It would not be the first time - to put it mildly - that a security proof has to be reconsidered.


How to figure out the size of the output of a cryptographic checksum function In Bishop's Introduction to computer security, on page 118, we see the following:

  Definition 8–2. A cryptographic checksum function (also called a strong hash function or a strong one-way function) $h: A → B$ is a function that has the following properties:

  For any $x ∈ A$, $h(x)$ is easy to compute.
  For any $y∈B$,it is computationally infeasible to find $x∈A$ such that $h(x)=y$.
  It is computationally infeasible to find $x, x' ∈ A$, such that $x ≠ x'$ and $h(x) = h(x')$. (Such a pair is called a collision.)

  The third requirement is often stated as:

  Given any $x ∈ A$, it is computationally infeasible to find another $x' ∈ A$
  such that $x ≠ x'$ and $h(x') = h(x)$.

  However, properties 3 and 4 are subtlely different. It is considerably harder to find an $x$ meeting the conditions in property 4 than it is to find a pair $x$ and $x'$ meeting the conditions in property 3. To explain why, we need to examine some basics of cryptographic checksum functions.

  Given that the checksum contains fewer bits than the message, several messages must produce the same checksum. The best checksum functions have the same number of messages produce each checksum. Furthermore, given any message, the checksum it produces can be determined only by computing the checksum. Such a checksum function acts as a random function.

  The size of the output of the cryptographic checksum is an important consideration owing to a mathematical principle called the pigeonhole principle.

  Definition 8–3. The pigeonhole principle states that if there are $n$ containers for $n + 1$ objects, at least one container will hold two objects. To understand its application here, consider a cryptographic checksum function that computes hashes of three bits and a set of files each of which contains five bits. This yields $2^3 = 8$ possible hashes for $2^5 = 32$ files. Hence, at least four different files correspond to the same hash.

  Now assume that a cryptographic checksum function computes hashes of 128 bits. The probability of finding a message corresponding to a given hash is $2^{–128}$, but the probability of finding two messages with the same hash (that is, with the value of neither message being constrained) is $2^{–64}$ (see Exercise 20).

How to get the final $2^{-64}$ mathematically?

The question states that the probability of finding a collision is $2^{-64}$. This is incorrect. The probability depends on the number of available messages, as we will see below.

If you take two random messages, the probability of them having the same $m$-bit hash is $2^{-m}$. So you're going to have to try around $2^{m}$ pairs before you find a collision.

But you can do this without generating $2^m$ messages.

Consider this:

With $n$ different messages, you can generate $C(n,2)$ different pairs of messages

$C(n,2) = \dfrac{n!}{2(n-2)!}$

$= \dfrac{n(n-1)(n-2)!}{2(n-2)!}$

$=\dfrac{n(n-1)}{2}$

$=\dfrac{n^2 -n}{2}$

So with $n$ different messages, we can generate $\dfrac{n^2 - n}{2}$ unique pairs.

Now we need to figure out how many messages are required to have a good probability ($\geq$50%) of finding two colliding messages.

$\dfrac{\frac{n^2 - n}{2}}{2^m} \geq 0.5$

$\dfrac{n^2 - n}{2^{m+1}} \geq 0.5$

$n^2 - n \geq 2^m$

So it turns out we need just over $2^{m/2}$ messages. This is usually simplified to exactly $2^{m/2}$ since we're dealing with such large numbers that the difference is negligible. There are other ways of calculating it, but they all work out to the same approximation (see Birthday Problem, Birthday Attack).


Formal relationship between encryption and random number generators? Cryptographically secure random number generators seem to have similar properties to symmetric encryption:

initial seed is permuted to produce a random numbers (key and ciphertext)
given the seed, they produce a random number that cannot be linked back to the initial seed (diffusion)
changing a single value in the seed results in multiple changes in the random number (confusion)

Is there a formal relationship between symmetric encryption and SRNGs?  I.e. is one a sub-set of the other?

Yes (loosely) and no (depending on your definition of a CSRNG).

A random number generator (restricting ourselves to Cryptographically Secure Random Number Generators) is actually a class of algorithms that produce a sequence of random numbers/bits - i.e. any sequence of numbers that is generated where the next part of the sequence cannot be predicted even with knowledge of the entire sequence to that point (with any non-negligible probability after a feasible amount of computation) can be a CSRNG, but a CSRNG can be constructed from cryptographic primitives in many different ways.

Symmetric encryption algorithms are generally either:

Stream ciphers, which are formally modeled as a Pseudo Random Generator or PRG. Technically these are usually a keystream produced by a PRG combined, e.g. by XOR, with the plaintext.
Block ciphers, which are formally modeled as a Pseudo Random Permutation or PRP.

Also in the general area of symmetric cryptography are Pseudo Random Functions or PRFs, which are often used as message authentication codes.

CSRNGs can be (and are) constructed from:

PRGs - a PRG is already a PRNG by definition.
PRPs - e.g. CTR_DRBG from NIST SP 800-90A
PRFs - e.g. HMAC_DRBG from NIST SP 800-90A. This also includes PRPs since a PRP is a pair of PRFs and you can just use the forward direction of the PRP.
(and also) hash functions - e.g. HASH_DRBG from NIST SP 800-90A

In practice a deployed CSRNG also involves gathering of entropy from the environment (otherwise it would use a static or predictable seed value, which would break the CSRNG contract) and other defensive measures to prevent the reverse-engineering of the internal state of the RNG.

Ignoring the entropy/seeding/defensive measures, if you consider a PRG to be equivalent to a CSRNG, then you can show a formal relationship to other symmetric cryptographic primitives since a PRG can be trivially constructed from any PRF (simply by using the PRF to encrypt an incrementing counter value).

As an interesting aside, PRGs, PRFs and PRPs can all be converted into each other using formal (although not necessarily efficient) constructions.


Does Mersenne Twister generate homogeneous numbers? I have been assigned to generate 15000+ homogeneous and uniform random numbers for a work.

I have been searching if Mersenne Twister generate homogeneous distribution of numbers but I don't find nothing. I have found a lot of test and proprieties but I do not know if any of those proprieties/tests refers to the homogeneity.

Can you explain me if the algorithm generates homogeneous numbers, why and what are the proprieties involved in?

By homogeneity I think that I mean this.

I think the Mersenne twister satisfies the requirement for homogeneity, since it produces numbers that are equally distributed (with 32-bit accuracy) in up to 623 dimensions.

But in a cryptography context, it could hardly be described as "uniform", because you only need to observe 624 outputs in order to predict all the following values with 100% accuracy.

I would recommend using a cryptographically secure PRNG such as AES-CTR instead. This should provide you with at least 100 MB of random data per second.


Scalar multiplication with projective coordinates I'm implementing point addition, doubling and scalar multiplication using projective coordinates. I took reference from this link https://www.nsa.gov/ia/_files/nist-routines.pdf

I have implemented

Routine 2.2.6(ec_double)

Routine 2.2.7(ec_add)

Routine 2.2.8(ec_full_add)

Routine 2.2.9(ecc_full_sub)

They all are working and I have verified the results with the example results given at the last for P-256 curve.

I implemented Routine 2.2.10 ec_mult(Scalar multiplication) But I couldnt get the correct output. In line 15 and 16 of this routine they take the binary representation of d(random number) and 3d. And the loop skips both MSB and LSB and performs the operations.

I got doubts like that 3d is modular multiplication or simple multiplication?. The loops runs for d or 3d if its not modular multiplication?

Is there anything else I'm missing out?. If somebody has followed this algorithm and implemented it please help me out here.

3d multiplication is a simple multiplication not a mod multiplication.

I suggest you to check IEEE Std 1363-2000 document and "A.10.3 Elliptic scalar multiplication" part of that document if you can.
It has somewhat more explanation than Nist's document.


Prove that the affine cipher over Z26 has perfect secrecy if every key is used with equal probability of 1/312 Prove that the affine cipher over Z26 has perfect secrecy if every key is used with equal probability of 1/312.

Just some guidance/help with this problem would be greatly appreciated not sure how to start the proof. Many thanks!

This would usually I think be more suited as a comment, but you were looking for guidance instead of a complete answer as it were, and I don't have enough reputation to comment.

I'd highly recommend Claude Shannon's introduction (the literal introduction, he developed the concept) to the question you pose. Here’s the paper (PDF) and the section is Part 10 on Pg. 679. The more broad statement of your question is Theorem 6, but he does (as he always does) an incredibly good job of approaching both the motivation for the theorem as well as the proof, the latter of which he gives in relatively informal way.


Rabin encryption when M is not Disjoint to n I need help with proving that the encryption going well when the message $M$ is not Disjoint to $n$ (public key).

Encryption message $\ C= M^2 \bmod n$

Decryption message $\ C^{(p+1)/4} \equiv ±M \bmod p$ and $\ C^{(q+1)/4} \equiv ±M \bmod q$.

Now, we can't use Fermat's little theorem.
Suppose that $M \neq 0 \pmod p$ and $M \equiv 0 \bmod q$

(because $n = pq$ and $p,q$ are primes)

The definition of the Rabin cryptosystem in the question likely is similar to:

Setup:

choose $p$ and $q$ large distinct primes with $p\equiv q\equiv 3\pmod 4$ ;
compute and publish public modulus $n=p\;q$, and publish it as the public key;
the private key is $p,q$ .

Encryption of message (representative) $M$ with $0\le M<n$ :

compute ciphertext $C=M^2\bmod n$ [implying by definition $0\le C<n$ ]

Decryption of ciphertext $C$ :

compute $M_p=C^{(p+1)/4}\bmod p$ and $M_q=C^{(q+1)/4}\bmod q$ ;
deduce that $M\equiv\pm M_p\pmod p$ and $M\equiv\pm M_q\pmod q$ [see proof at end];
noticing that $\gcd(p,q)=1$ by construction, use the Chinese Remainder Theorem to find the set $\mathcal M$ of possible $M$ as follows:

compute $q_\text{inv}=q^{-1}\bmod p$ [this value can be reused for multiple $C$ ];
compute these 4 values:
$$\begin{align}
M_0&=(q((q_\text{inv}(M_p-M_q))\bmod p)+M_q)\bmod n\\
M_1&=-M_0\bmod n\\
M_2&=(q((q_\text{inv}(M_p+M_q))\bmod p)-M_q)\bmod n\\
M_3&=-M_2\bmod n
\end{align}$$
the set $\mathcal M$ is $\{M_0,M_1,M_2,M_3\}$ ;

select $M$ as the message in $\mathcal M$ that pass some consistency check.

Further, it is commonly restricted to $p\ne q\pmod8$ at setup, yielding $n\equiv5\pmod8$; and $M\equiv4\pmod8$ [or some other value $\pmod8$ ], which then is enough to always allow recognition of which element of the set $\mathcal M$ is $M$.

Depending on $M$ or $C$, the set $\mathcal M$ will have one, two or four distinct elements. One element only occurs for $M=0$ ($M_p=M_q=0$); two elements occur when otherwise $\gcd(M,n)\ne1$ [equivalently, when a single of  $M_p=0$ (x)or $M_q=0$ holds; or in other words, when $M\ne0$ is not disjoint to $n$ ; ]; four elements occurs otherwise, that is for overwhelmingly most $M$.

The original reference on the Rabin encryption scheme is: Michael O. Rabin; Digitized Signatures and Public Key Functions as Intractable a Factorization, MIT-LCS-TR-212 (1979). It defines $C=M(M+b)\bmod n$ for some public $b$ with $0\le b<n$, which makes the cryptosystem somewhat less malleable; also, it is not restricted to $p\equiv q\equiv 3\pmod 4$.

Proof that for all $M$, it holds $C^{(p+1)/4}\equiv\pm M\pmod p$ [same for $q$ rather than $p$ ]

By construction, $C=M^2\bmod n$, and $p$ divides $n$; therefore $C\equiv M^2\pmod p$
$p\equiv3\pmod4$ therefore $(p+1)/4$ is an integer, and we can raise the above to that power, giving
$$\begin{align}
C^{(p+1)/4}&\equiv(M^2)^{(p+1)/4}&&\pmod p\\
C^{(p+1)/4}&\equiv M^{(p+1)/2}&&\pmod p\\
C^{(p+1)/4}&\equiv M\cdot M^{(p-1)/2}&&\pmod p&&(1)
\end{align}$$
If $M\equiv0\pmod p$ :

by Fermat's little theorem, and since $p$ is prime, $M^{p-1}\equiv1\pmod p$ holds;
define $X=M^{(p-1)/2}\bmod p$ [implying by definition $0\le X<p$ ]; the above becomes $X^2\equiv1\pmod p$, that is $(X+1)(X-1)\equiv0\pmod p$, which  has exactly two solutions $X=1$ and $X=p-1$ ;
therefore $M\cdot M^{(p-1)/2}\equiv\pm M\pmod p$ ;

Otherwise [ that is, when $M\equiv0\pmod p$ ]

$M\cdot M^{(p-1)/2}\equiv\pm M\pmod p$ holds [both sides are $0\pmod p$ ];

Replacing in $(1)$, it comes $C^{(p+1)/4}\equiv\pm M\pmod p$ for both cases.


Crypto-shredding a file by erasing the IV instead of erasing the Key Imagine an authenticated, encrypted file system, which uses AES-256-CTR to encrypt a 64 KB file sector, then uses HMAC-SHA256 to authenticate the 64 KB file sector (including the IV). IVs are 128-bit, randomly generated.

The global 256-bit encryption and 256-bit authentication keys are independent of each other, and are used across all files (i.e. no per-file keys).

The file system needs to be able to crypto-shred individual files, and needs to sustain 100,000 IOPS.

How would you implement crypto-shredding without deriving per-file keys per operation (or without caching thousands of derived per-file keys in memory)?

Instead of deriving per-file keys, would XORing the stored public sector IV with a secret per-file SALT be adequate? In other words, the random IV (which is stored on disk) would be XORed with a secret per-file SALT when encrypting or decrypting. Assume the per-file SALT can be erased when the file needs to be crypto-shredded.

This should avoid the need for 100,000 HKDF or PRF calls per second to derive per-file keys.

Crucially, since the system is garbage collected, this would also avoid having 100,000 derived per-file keys scattered throughout memory at any point in time, and avoid bugs related to the caching and versioning of these keys.

Crypto-shredding usually operates by erasing the key, but erasing the SALT used to generate the final IV seems to make more sense. I don't know if I'm missing something here?

No, just erasing the AES-CTR IV is not enough to reliably render the file undecryptable.

To see why, consider what happens if the AES key is later compromised, and the attacker also happens to know at least one AES block (i.e. 16 bytes) of the "shredded" file's plaintext content.  They can then XOR this known plaintext with the corresponding part of the ciphertext to obtain a block of the AES-CTR keystream.

Running this block through the AES block decryption function, using the compromised key, will then reveal the input block (i.e. nonce and counter) used to generate this block of keystream.  Incrementing and/or decrementing the counter will then let the attacker decrypt all other blocks of the file.

Ps. Similar attacks are also possible on all the other classical block cipher modes of operation (CBC, CFB, OFB, CTR).  I'll leave figuring out the exact steps needed as an exercise.  (The diagrams on the Wikipedia page I linked to should be helpful.)  With CBC and CFB modes, the first block of the file cannot be decrypted without knowing the IV, but on the other hand, those modes allow all the rest of the file to be decrypted even without knowing any of the plaintext in advance.

Modern AE modes aren't generally any more resistant to such attacks, either, especially as most of them simply combine one of the classical modes (usually CTR) with some message authentication scheme, and can thus be attacker just like the underlying classical mode.

The take-home message from all this is that the IV is not a secret, and hiding it is not sufficient to protect the message from decryption by anyone who has the key.  More generally, modern encryption schemes are generally designed with the assumption that the only secret parameter of the system is the key, and with the goal of remaining unbreakable as long as the attacker does not know they key.  The flip side of the coin is that, if the attacker does know the key, these schemes generally offer no security guarantees whatsoever.


How do you use the Tiger hash function with GPG? I've searched Google and the GnuPG documentation and I haven't been able to find an answer. Some pointers in the right direction would be greatly appreciated.

The Tiger hash function is not part of the OpenPGP standard which GnuPG implements. A previous version of that standard (RFC 2440) had reserved an identifier for Tiger, but without actually standardizing it (no OID formally assigned). This was removed during elaboration of the next (current) version of OpenPGP, circa 2003, with apparent consensus, on the basis that having too many options may be detrimental to deployment and interoperability.

Older versions of GnuPG did implement the Tiger hash function, outside of the standard (by definition) but this was removed as well; apparently, the most recent version of GnuPG which still supported Tiger was version 1.2.6 (from 2004). So, to answer your question: right now, and for the foreseeable future, you do not user Tiger with GnuPG.


How to check a signed CSR with openssl? I just learned that a CSR can be signed. See this Why is a CSR signed and which key is used for signing?

I tried to check the csr with below openssl command, but failed with errors "139942025398160:error:0906D06C:PEM routines:PEM_read_bio:no start line:pem_lib.c:707:Expecting: CERTIFICATE REQUEST"

  openssl req -in signed_csr_file.scsr -noout -verify

Does anyone know how to check signed csr with openssl ?

Thanks

First, there are several certificate-request schemes (and formats) in use. Are you sure this file is supposed to be a CSR in the specific format supported by req namely PKCS10/rfc2986 et pred?

Second, what is actually in the file? Is it actually in PEM format as described in wikipedia's second paragraph i.e. a five-dashes-BEGIN-something line, some base64, and a five-dashes-END-something line, and if so what exactly is the 'something'? Is it CERTIFICATE REQUEST or NEW CERTIFICATE REQUEST or something else? Is the PEM format exactly correct (no missing, altered, or extra characters within the lines of the PEM block -- extra lines before or after are okay)?

If the file is not PEM format, what is it? If it contains unprintable characters, use a hex dump or similar. If you don't recognize it, post it, or at least the first 50-100 bytes, for us to look at.


Public Key Encryption, how do you handle not trusting the middle man? With public/private key encryption you must trust the central authority correct?

What can you do if you don't want to trust the centeral authority? Are there any ways around that?

for example in a chat app

I imagine, no matter what, you will have to make the client open source so as to keep it known you are not saving the users private keys.

With public/private key encryption you must trust the central authority correct?

Not quite.  The honest parties must have an authenticated (but not necessarily confidential) channel to obtain each other's public keys.  A central authority that both parties trust is one way of fulfilling that requirement, but is not the only one.  For example, public keys could instead be exchanged through a face-to-face meeting.

  What can you do if you don't want to trust the centeral authority? Are there any ways around that?

  for example in a chat app

Apps like Signal and WhatsApp provide two authentication methods:

Use the service itself as a "central authority" that provides you with your contacts' public keys.
Out-of-band contact verification through security codes, which users can compare independently to verify that the central authority is not cheating them.

From Signal's support page on this:

  Each Signal conversation has a unique safety number. The safety number gets stored the first time you exchange a private message with a new contact. You will be alerted if a conversation's safety number ever changes. This can happen if someone else is pretending to be them, or if they get a new phone and reinstall Signal.

  [...] The safety number on your phone should match those on your contact's phone. If the safety number is identical then you can be sure that you are communicating with the right person. If the safety number does not match, then make sure you and your contact are using updated versions of Signal, open a conversation with just that contact, and then try again.

WhatsApp has a similar feature as well:

  Each of your chats has its own security code used to verify that your calls and the messages you send to that chat are end-to-end encrypted.

  Note: The verification process is optional and is used only to confirm
  that the messages you send are end-to-end encrypted.

  This code can be found in the contact info screen, both as a QR code
  and a 60-digit number. These codes are unique to each chat and can be
  compared between people in each chat to verify that the messages you
  send to the chat are end-to-end encrypted. Security codes are just
  visible versions of the special key shared between you - and don't
  worry, it's not the actual key itself, that's always kept secret.

If this is something that concerns you at all, you should be at least on occasion   checking your conversations' security codes when you meet your contacts in person.  For such services not to be abused for mass surveillance, a small but significant percentage of users need to periodically exercise this kind of vigilance.


Are there any other highly trusted and secure symmetric encryption algorithms besides AES? AES is the gold standard for symmetric encryption. It is highly trusted and highly secure. Do any other symmetric ciphers - besides OTP - come close to AES's usability, security, trust-ability?

ChaCha20

Provides 128 or 256-bit key space.
The best attack against 6 (128-bit) or 7 (256-bit) of 20 rounds
Stream cipher requires 64-bit nonce and 64-bit position counter
Used in TLS 1.3, OpenSSH, as well as BSD and Linux kernel RNGs
Part of ESTREAM portfolio

Serpent

Provides 128, 192, or 256 bit key space.
Best attack against 11 or 12 of 32 rounds
Block cipher with 128-bit block
AES competition finalist

Twofish

Provides 128, 192, or 256 bit key space.
Best attack against 6 of 16 rounds
Block cipher with 128-bit block and Feistel network design
AES competition finalist
Used in disk encryption software, OpenPGP standard, numerous applications

Deoxys-II

It provides 128 or 256-bit keyspace.
Authenticated encryption scheme with a 120-bit nonce, nonce misuse resistant
Based on 16-round tweakable block cipher using AES round function
Designed to provide better security than AES-GCM
Part of CAESAR portfolio for use case 3 (maximum security)

Camellia

Provides 128, 192, or 256-bit key space.
Block cipher with 128-bit block and Feistel network design
Patented but royalty-free
Used in OpenSSL, optional in OpenPGP and numerous other standards
Part of NESSIE and CRYPTREC portfolios

SEED

Provides 128-bit key space.
Best attack against 8 of 16 rounds
Block cipher with 128-bit block and Feistel network design
Used primarily in South Korea

CAST-256

Provides 128 to 256 bit security in 32-bit increments
Best attack against 28 of 48 rounds
Block cipher with 128-bit block and Feistel network design

There is the generic multi-target attack on n-bit key ciphers that requires less than the $2^n$ cipher evaluations.


Why does choosing the first coprime e greater than half of φ(n) result in the same d (private exponent) While reading on RSA's algorithm, I attempted a simplified implementation and noticed the following:

When choosing the public exponent $e$, if the value chosen is the first coprime after $φ(n)/2$ then the resulting public and private exponents are equal.

Example:
$p = 67\\q = 53\\n = 3551\\φ(n) = 3432$
$e = 1717$ i.e first coprime of 3432 greater than half
$d = 1717$ where $d \times e\ mod\ φ(n) = 1$
resulting in no encryption
$c(41) = 41^{1717}\ mod\ 3551 ≡ 41$

Problem might be in my code?

So I guess my questions are:

Why does this happen?
Is this even a problem?
What am I missing?

Selecting only public exponents that are primes might eliminate the possibility of this occurring, but I have neither tested nor seen that it's a requirement in the RSA algorithm.

When choosing the public exponent $e$, if the value chosen is the first coprime after $\phi(n)/2$ then the resulting public and private exponents are equal.

Well, yeah, that'll always be true.

  Why does this happen?

We have $e=d$ whenever we have both of the following true:

$$e^2 \equiv 1 \pmod{p-1}$$

$$e^2 \equiv 1 \pmod{q-1}$$

Now, if $e = (p-1)(q-1)/2 + 1$ (which is always the first coprime after $\phi(n)/2$), then if we denote $k = (q-1)/2$ (which is an integer),

$e^2 = ((p-1)(q-1)/2 + 1)^2 = ((p-1) k + 1)^2 \equiv 1^2 = 1 \pmod{p-1}$

By symmetry, we also have $e^2 = 1 \pmod{q-1}$ as well, and so $e=d$ works in this case.

Furthermore, whenever we have both the following hold:

$$e \equiv 1 \pmod{p-1}$$
$$e \equiv 1 \pmod{q-1}$$

then we'll have $M^e \equiv M \pmod{N}$ (for all $M$), that is, the RSA operation will always give us the original plaintext.  These are also both true in the case of $e = \phi(N)/2 + 1$, and so such an $e$ will also always have plaintext=ciphertext, which is what you observed.

  Is this even a problem?

If you intend to use $\phi(n)/2 + 1$ as your public exponent, yeah, that's a problem.  Exposing such a value also makes $n$ easy to factor; however the attacker doesn't need to factor to break the system in this case.

However, if you use a more normal public exponent, say, 3 or 65537, it's pretty irrelevant.

  Selecting only public exponents that are primes might eliminate the possibility of this occurring, but I have neither tested nor seen that it's a requirement in the RSA algorithm.

Well, what's most common for RSA implementations is to pick $e$ first (and it makes sense to pick it as a small value), and then select primes $p$ and $q$ such that $p-1$ and $q-1$ are relatively prime to $e$.  If you do that, then $e=d$ cannot happen, because if $1 < e < \sqrt{p-1}$, then we trivially have $e^2 \not\equiv 1 \pmod{p-1}$.

However, even if you pick $e$ large (for whatever reason), as long as you do it randomly, then the probability that both $e^2 \equiv 1 \pmod{p-1}$ and $e^2 \equiv 1 \pmod{q-1}$ both hold is negligible.


Diffie-Hellman Application Alice and Bob want to perform a Diffie-Hellman key exchange using the group $G$, a
primitive root $g$, Alice’s secret key $k_A$ and Bob’s secret key $k_B$. In each case below
compute the element of $G$ that Alice sends to Bob, the element that Bob sends to
Alice, and the secret key that Alice and Bob will share.

$G=\mathbb Z/163\mathbb Z$(as an additive group), $g = 2$, $k_A = 128$, $k_B = 65$.
$G=\mathbb F_{163}^*$, $g = 2$, $k_A = 128$, $k_B = 65$
$G = [0, 1) ∩ \mathbb Q$ with group operation
$$a\Diamond b = [a + b] = a + b − \left \lceil{a+b}\right \rceil$$
$g = 23/123$, $k_A = 358$ and $k_B = −44$.
$G = GL_2(\mathbb F_{17})$, $g= \left[\begin{array}{ c c }
     2 & 3 \\
     4 & 5
  \end{array} \right]$, $k_A = 13$, $k_B = 5$.

For $1)$  I did the following, Alice sends Bob $A = (128)2 \bmod p$ and then Bob sends Alice $B = (65)2 \bmod p$. Their secret key is $(128+65)2 \bmod p$.

For $2)$ I did this: Alice sends Bob $A = 2^{128}$ $mod p$ and Bob sends Alice $B = 2^{65} \bmod p$ Therefore, their secret key is $B = 2^{(65)(128)} \bmod p$.

For $3)$ Alice sends Bob $128\Diamond 23/123$ and Bob sends Alice $65\Diamond 23/123$ so their secret key is $(128\Diamond 65)\Diamond 23/123$. However I don't know whether this is right or not.

I don't know how to do the fourth one.

Any help is appreciated. Thank you.

Eve shouldn't be able to find the shared secret easily from the messages Alice and Bob send.

In the questions 1 and 2, you said that the shared secret is the sum/the product of the two messages, but anyone can compute them. Therefore, you are wrong.
The shared secret should be:
1) $B=(128)(65)2 = (65)(128)2\mod p$,
2) $B=(2^{(65)})^{(128)}=(2^{(128)})^{(65)}\mod p$.

Once you understood these two examples, I am sure you will be able to solve the 2 other questions easily by thinking a bit more about it.

Edit: you're right about 2).


Implementing 5 modes of operation with a hash function Is it possible to implement any of the 5 modes of operation (ECB, CBC, OFB, CFB, CTR) with a hash function?

The modes you are referencing are specifically modes of operations for block ciphers, and therefore are not directly applicable to hash functions. Block cipher operations take 2 inputs, the key and a block-sized input value, and output a block-sized keyed permutation of the input. Hash functions take a variable length input, and output a fixed length value.
However, the way 3 of them work can be applied hash functions, by using HMAC or NMAC to turn the hash into a keyed pseudorandom function.
CTR:
In the block cipher we have:
$C_i = P_i \oplus Enc_k(Nonce \ || \ Ctr_i)$
Applying to the hash we have:
$C_i = P_i \oplus HMAC_k(Nonce \ || \ Ctr_i)$
OFB:
In the block cipher we have:
$O_0 = IV$
$O_i = Enc_k(O_{i-1})$
$C_i = P_i \oplus O_i$
Applying to the hash we have:
$O_0 = IV$
$O_i = HMAC_k(O_{i-1})$
$C_i = P_i \oplus O_i$
CFB:
In the block cipher we have:
$C_0 = IV$
$C_i = P_i \oplus Enc_k(C_{i-1})$
Applying to the hash we have:
$C_0 = IV$
$C_i = P_i \oplus HMAC_k(C_{i-1})$
Because of the way these modes work, by not requiring the decryption operation, a keyed one-way function can perform the same function, which is the cryptographic transformation of the input to XOR against the plaintext and generate the ciphertext. They make these schemes stream ciphers.
Because the output size of secure hash functions (SHA256 or SHA512) is generally larger than the block size of a block cipher (AES), using these hash functions may be able to encode a larger amount of plaintext before running into the problems these modes may experience with block ciphers. The additional flexibility of a variable length input also allows the hash functions to have larger nonces/IVs.
However since they are not permutations, the security proofs that apply to block ciphers may not apply to hash functions when used in these modes. Additional security may be provided by truncating the output of the hash function before encrypting the plaintext, but still feeding the full output back in the case of OFB and CFB.
From a performance perspective, most hash functions are slower than most block ciphers, by a wide margin. Using HMAC also requires additional hash operations to generate the secret initial values, however an implementation can do these once per plaintext if the IV and input length of a hash function can changed arbitrarily.


Encryption through multiplication of encoded key Yesterday I finished programming my own encryption program. It is using an input and a key. Here are all the steps it is going through. For an example, let say the input is "Hello" and the key is "Hi"

You take the input and convert it into binary:

01001000 01100101 01101100 01101100 01101111

You make this Binary string into one long string:

0100100001100101011011000110110001101111
You convert this long binary number into a decimal number:

0100100001100101011011000110110001101111 = 310939249775
You do the same 3 steps above with the key. So the key "Hi" in Decimal is:

18537
You now take the length of the key, in this 2 because "Hi" has 2 characters.
You multiply the two decimal value, and multiply that by the length of the key:

310939249775*18537*2 = 11527761746158350
You lastly convert this big number into Base36(0-9 a-z). This is the final output:

35i90mxoaa6

Now this is how my encryption program works. You can reverse this my dividing the numbers. If someone only has the output but not the key, he has no way to get to the original message right? Also, if this doesn't exist, can I name this the way I want?

It is insecure in the sense that anybody with a calculator can reverse it (and a large set of people without one).

According to the Kerckhoff principle you should tell everybody the algorithm. So there is no security there.

After that an attacker will receive multiple ciphertext (ciphertext only attack). This attacker will quickly find a common divisor for the ciphertext. This common divisor is the key.

Furthermore, there are special values in your plaintext. In principle you don't want to have these in a cryptographic algorithm. Say for instance that you send a single space. In that case you would send bit string 00100000. As you can see there is only one bit set. Multiplication will result in a binary representation of the key "Hi", shifted 5 bits to the left. So an attacker can simply read the key straight from memory. If you can think of such a value, then your cipher is already considered broken.

Finally, a good cipher is a random permutation; a 1:1 mapping of the key to the ciphertext. That's the case in your algorithm, but the permutation is from $N$ to a set $key \times N$. Now you would have to encode this ciphertext efficiently or you end up with very large ciphertext values. This is why most cryptography uses modular arithmetic and XOR (which can be thought of as addition modulus 2).


Calculate RSA private exponent when given public exponent and the modulus factors using extended euclid I was reading this  answer that shows how to calculate the inverse of public exponent, i got to the point where we apply the euclidean algorithm and finish substituting to get

(40−2×17)−1×(17−2×(40−2×17))=1

it states "this is a linear combination of 17 and 40, after simplifying you get:"

(−7)×17+3×40=1

which gives us the d = -7

but i'm stuck as to how we simplified down to

(−7)×17+3×40=1

from:

(40−2×17)−1×(17−2×(40−2×17))=1

i would be grateful if someone could explain it to me

Thanks in advance

Try just expanding the parentheses. Once they're all gone, collect all the multiples of $40$ and $17$ together:

$(40 - 2 \times 17) - 1 \times (17 - 2 \times (40 - 2 \times 17)) = 1$

$1\times40 - 2 \times 17 - 1 \times 17 + 2 \times (40 - 2 \times 17) = 1$

$1\times40 - 2 \times 17 - 1 \times 17 + 2 \times 40 - 4 \times 17 = 1$

$(1 + 2)\times40 - 2  \times 17 - 1 \times 17  - 4 \times 17 = 1$

$(1 + 2)\times40 - (2 + 1 + 4) \times 17 = 1$

$3\times40 - 7 \times 17 = 1$, or

$(-7) \times 17 + 3\times 40 = 1$


RSA reconstructing private key knowing MSBs PREMISE: This question is purely theoretical because usually an attacker will not know private exponent d and can't compare it with obtained MSB bytes.

Suppose an RSA 1024 bit signature.

An attacker through a key exposure obtain the half most significant bytes of the private exponent d.

Can the attacker reconstruct the LSBs of d without bruteforce the LSB part? Can he make it in a reasonable amount of time?

There are best way to do it?

I do not believe that there is any reasonably efficient way to reconstruct the lsbits; if there were, then a good fraction of the RSA keys out there could be efficiently factored (!).

Here's why: a lot of RSA keys have a modulus $n = pq$, where $p$ and $q$ are primes of equal size.  Then, let us assume a small $e$ (it needs to be relatively prime to $p-1$ and $q-1$; we could use the $e$ in the public key, or pick our own and hope we're lucky).  Then, the relationship between $d$ and $e$ is:

$$de \equiv 1 \pmod{lcm(p-1, q-1)}$$

which we can rearrange into

$$d = (k(n - p - q + 1)/\gcd(p-1, q-1) + 1) / e$$

where $k$ is some unknown integer that turns out to be within the range $(0, e)$.  If we're interested in only the msbits of $d$, we can simplify this to:

$$d \approx (k (n + \epsilon) / (e \cdot \gcd(p-1, q-1)$$

Where $\epsilon < 5\sqrt{n}$.  We can guess $k$ and the contibutions of $\epsilon$ on $n$, and $\gcd(p-1, q-1)$ is likely to be a small even value; going through the possibilities, that gives us reasonable guesses for the msbit's of $d$; if one is correct, then we could use the assumed method to reconstruct the lsbit's, and then immediately factor.


EL gamal cryptosystem I have this question which gives me q=71(my prime number) , a=7(generator), Yb=3(public key), m=30(message), c1=59(first cipher text) and he wants me to find c2 (second cipher text)
I know  that c2 = rM (r:one time key) , which means I have to find r=Y^k or r=c1^x but I dont have k nor x. The only solution is to solve the DLP is there any solution beside this?

Ok, so now the question makes more sense to me.

Yes you are correct. Sadly, you cannot solve the problem without solving the DLP. This is simply because in the problem he didn't share his secret x or y. If he had shared y. You could have solved it. But your space is quite small, so it's not too hard to solve.

Public key = g^x = 7^x = 3 (mod 71)
Private key = x = 26 (since this is 7^26 == 3 mod 71) (DONT KNOW THIS)

C1 is :

C1 = g^y = 7^y = 59 (mod 71)
Private key = y = 3 (since this is 7^3 == 59 mod 71) (DONT KNOW THIS)

Message is mapped to:

m' = m mod 71
m' == 30 mod 71

Thus to find c2 you need:

c2 = m' * g^(xy)

But since you know neither x nor y you can't solve it. (of course the sample space was small so I could find it).

First find g^xy

g^(xy) = (g^x)^y = (3)^3 = 27

Your solution should thus be:

c2 == 30 * 27 (mod 71)
c2 == 29 (mod 71)

Hope that helps!


Mixing Cipher Lower Bounds Let Z be a cipher system consisting of three m-sequence linear feedback shift registers (LFSR) of length 128 bits each which are assumed to be not cryptographically secure and the registers are seeded with IID variables. Lets identify the registers as S for select register, C for the ciphertext register, and D as the decoy register. The enciphering system works as follows:

The output bits of S control the select line of a two input multiplexer with one input being the XOR of the message bits with register C(call these the ciphertext bits as is the usual custom) and the other input being the bits of D, the decoy register.It is assumed that the message bits are held in a buffer until they are selected for output but register C is continually clocked even if it is not selected, so C is constantly losing information ,likewise with register D. So the output of the multiplexer is a pseudorandom mixture of ciphertext bits with decoy bits. In order for the adversary to recover the message he/she must first separate the ciphertext bits from the decoy bits. Of course this is not a very efficient way to encrypt information because by adding decoy bits to the ciphertext bits effectively doubles your information traffic, but let's say we don't care about efficiency. How could an adversary separate the ciphertext bits from the decoy bits in polynomial time, neither bitstream gives any information about the other and nothing about the select bits S.

The design you described is very close to Geffe generator - it consists of three LFSRs L1, L2, L3 and the output bit is either the output of L2 or L3 depending on the value of the output bit of L1. Essentially, the output filter function is $F(x1, x2, x3) = (x1\wedge x2) \vee (\neg x1 \wedge x3)$.

A classical way of attacking Geffe generator is the correlation attack - Google search for "Geffe generator attack" yields a number of relevant results. It looks like this type of attack would be also applicable to your case.
Another potential attack avenue would be algebraic attacks - output bits are quadratic function of the variables of the internal state, so it might be possible to do linearization attack if you observe enough bits of the output or you have additional data about the content of the registers (e.g. you know decoy bits).

In cryptanalysis, the devil is really in the details, so without posting a full description of the algorithm and a reference implementation, it's difficult to say much more than I already wrote above. This should be a good starting point though.

One more remark regarding attack complexities - while I don't think there is a polynomial time attack on a generator you describe, what we care in practice is concrete (not asymptotic) complexity of the attack. If one can show an attack that has smaller complexity than the best generic attack, it is considered a break of the algorithm.


Toy one-way hash function for six digit number I need to copy some data from a secure server to my laptop to work on it with a program (this description is very vague, I know). The data have six digit employee numbers and we are strictly prohibited from downloading data with these.

I was wondering if there is a really simple hash function I could put in a spreadsheet to convert these employee numbers into a one way hash so I can download these? All I care about is being able to tell which data came from the same employee number. I am not terribly concerned about a few collisions either, the set is small enough I could look for those.

I was thinking some simple xor with an added salt or squaring and taking some digits but everything seems like it would be too guessable especially if there is a series of sequential employee numbers in a row.

For example, hash

123456

to somerandomlookingstring, but I need to be sure the next result is

123457

is not terribly similar, so not like: somerandomlookingstrifh

I feel like this is something hardcore crypto people may know off-hand, some mini ancestor of MD5, some evolution of ROT13, but light enough for thousands of spreadsheet cells.

A six digit integer gives you a possible one million possible IDs. Consider this python code that hashes every possible ID using a properly vetted, secure, cryptographic hash function:

import hashlib
import time

t0 = time.time()

for i in range(1000000):
    hashlib.blake2b(bin(i).encode("utf-8"))

t1 = time.time()

print(t1-t0)

It runs in around 400ms on my laptop. An attacker could generate a look-up table in less than a second that would map these output hashes back to the original employee numbers that they derive from.

In order to combat this, you'd have to use some kind of "hard" cryptographic hash like Argon2 or PBKDF2 in order to ramp up the computational complexity of generating a rainbow table.

But really this is just pushing the problem down the road and making it more difficult for yourself as well.

The better solution is to generate your own random lookup table and use that as a substitution in your spreadsheet. Consider:

import secrets

lookup = {}

for i in range(1000000):
        lookup[i] = secrets.randbelow(1000000)

# employee id "662893" is mapped to which masked value?
print(lookup[662893])

The code is not quite what you want as there's no padding to six digits and the reverse lookup is likely the more useful one, and it does not check for collisions, but it serves to make the point.

Tackling collisions can be done by selecting IDs from the set of unused IDs, or just increasing the length of the random values so that the probability of collisions becomes negligible.

In this scheme where each employee is mapped to a unique ID, an attacker has no way of computing the original employee ID from the masked value without the lookup table, as they were generated randomly.

If the small (2x) memory overhead of this solution is unacceptable, Maarten's solution of using a keyed hash function is also viable. Simply use a HMAC construction with a secure hash function and a 32 byte key, and the attacker would have no way of bruteforcing the inputs without knowing the key.


How to store and use a Cryptographic Seed in a database Companies such as Barclays use cryptographic seeds (for their PINsentry system), RSA do the same for RSA SecurID, but how do they safely secure the seeds in the database.
With passwords you just hash it at and add a salt, but the server must know the original seed to verify the users code, the one-time password generated from the seed.

The best way to encrypt a seed in a db would be to use multiparty computation and heterogeneous computing (multiple core systems). The only other way would be to store them in plaintext, e.g. in a shadow password (non-public file).


Securing http session id's by appending HMAC hash? First, I apologize if this question is off topic as defined here. If so, please let me know and I'll close it.

I'm building a sessions middleware for an http service and thought it might be a good idea to append hmac hashes of session id's, rather then setting bare session id's in cookies, but am a bit of a crypto novice. FYI - the service isn't protecting anything critical, it's just a side project of mine, which is why I'm rolling my own solution.

First, allow me to layout the general sessions design, and I'll follow with some specific questions. Here is an overview of my sessions service:

Generate a random session id using an RFC 4122 version 4 uuid generator. I store this id in redis along with some other info (userID, expiry, etc.).
Hash the byte array of this session id with hmac sha512. My hashing key was generated with openssl $ openssl rand -base64 64
Append the bytes of the hmac hash to the the byte array of the session id. Base64 encode the resulting array, stringify and set as an http only, secure cookie.

Upon receiving a request from a client, verifying the user session is basically the steps above, but in reverse.

My questions are:

Does appending the hmac hash to the session id offer any benefit above and beyond simply setting a version 4 uuid to the cookie? My thought was that I could verify the hmac signature using my key before pinging my db to check if the session id was expired. This would cut down trips to my db if someone were trying to guess at session id's.
Is sha512 overkill for hashing my session id? My understanding is that it should be faster on a 64 bit machine.
Is appending the hashed bytes array to the session id bytes array, base64 encoding and stringifying the result the proper way of storing this information in a cookie?
Is $ openssl rand -base64 64 the proper way of generating a key for my purposes? Based on this discussion, my understanding is that my key length should optimally be between 64 and 128 bytes.
Anything else you want to add? Anything I've overlooked?

Thanks for your input. Cheers!

1. Does appending the hmac hash to the session id offer any benefit above and beyond simply setting a version 4 uuid to the cookie?

As you found out yourself, The main benefit is eliminating the database query for authenticating the cookie.

2. Is sha512 overkill for hashing my session id? My understanding is that it should be faster on a 64 bit machine.

The storage/bandwidth constraint is probably more significant than the speed constraint, as cookies are limited to 4K. So as a general design guideline it would be better to use a 256 bit hash. You can achieve that by using only 256 bits from the hash generated by SHA512.

3. Is appending the hashed bytes array to the session id bytes array, base64 encoding and stringifying the result the proper way of storing this information in a cookie?

This is not really a cryptography question but a software engineering question. In a nutshell, you'd want the cookie to be formatted such that you and others will be able to debug problems and fix your code even long into the future.

4. Is $ openssl rand -base64 64 the proper way of generating a key for my purposes? Based on this discussion, my understanding is that my key length should optimally be between 64 and 128 bytes.

Once again a software engineering question. Assuming you write your code in some programming language other than bash, you're better off using a cryptography library for this language. As for the key length, 32 bytes (256 bits) should be enough.

5. Anything else you want to add? Anything I've overlooked?

Try looking at the implementation of established libraries. Not sure what you want to use this for and which language you'll be using, so it is hard to give the right recommendation. One Python example that pops into mind is this but once again maybe you're into a different use case.


Double Encrypting with two different keys In terms of security, would it be MORE or LESS secure to take, say, an RC4 output (or Serpent) or other, that is encrypted with one key, and to encrypt that output with AES (using a different key)?

> $Data -> Serpent ->  key: $s_key = HASH_HMAC(sha256, "1st Key" .
> $salt1, "HMAC KEY1") = $S_Output
>
> $S_Output -> Rijndael (AES) -> key: $aes_key = HASH_HMAC(sha256, "2nd
> Key" . $salt1 . $s_key . $salt2, "HMAC KEY2") = $AES_Output

As long as I'm using good hashes as keys, would this be MORE secure than using a single key with AES? Is there a risk of the two ciphers colliding in some fashion? If so, would using a stream cipher instead of another xor-type cipher avoid this?

P.S. THIS IS PSUEDO-CODE -- I will be using truly random salts and keys for my data i.e. mcrypt / openssl

I will be using a software based token system like the RSA SecurID that is on a fingerprint-secured thumbdrive that opens a self-contained browser. Each keyholder has a 512 bit has to open the soft-token automatically. Once the token is posted to the auth site, it gives the pair (two people) 90 min to enter the keys.

Repeat the same thing for user# 2 with the second key.

AND THE REAL KICKER -- aside from the php thumb drive token gen, THIS HAS TO RUN ON PHP, killing the possibility of many other libs that are ideal.

Basically, two biometric token systems + two passphrases within 90 mins decrypts the file. But better to use Serpent + AES, AES + AES, or TWOFISH + AES?

I don't think it's a bad idea - neither does Bruce Schneier.  In his book Applied Cryptography, there is a section called "Cascading Multiple Block Algorithms". He basically states that provided that two distinct algorithms and two independent keys are used, then the result should be at least as difficult to break as the strongest algorithm.

If Alice and Bob do not trust each other’s algorithms, they can use a cascade. If these are stream algorithms, the order doesn’t matter. If they are block algorithms, Alice can first use Algorithm A and then use Algorithm B. Bob, who trusts Algorithm B more, can use Algorithm B followed by Algorithm A. They might even add a good stream cipher between the two algorithms; it can’t hurt and could very well increase security.
Remember that the keys for each algorithm in the cascade must be independent. If Algorithm A has a 64-bit key and Algorithm B has a 128-bit key, then the resultant cascade must have a 192-bit key. If you don’t use independent keys, then the pessimists are much more likely to be right.


Salsa20 as a PRNG with streams Can I use Salsa20 as a good non-cryptographic PRNG with different streams if I reduce the number of rounds to 8 and omit the addition step at the end? I want to omit the final step because I don't want to get all zero outputs.

Reducing the rounds to 8 would give you Salsa20/8, which is not just a fast PRNG operating at 1.88 cycles per byte on Core2Duo, but is still quite cryptographically secure with the best attack requiring approximately 2244 operations. Removing the final addition step would not be good though, as without that, it would be trivial to reverse the function and discover the key and counter given just a single block of known plaintext. You will not get all zero outputs by keeping the addition, so you should keep it.

You could cut the algorithm down to four rounds in order to roughly double the speed while completely sacrificing cryptographic security. Less than four rounds results in incomplete diffusion, leading to biased and non-uniform output. However, it will still be roughly twice as slow as the fastest dedicated non-cryptographic PRNG, XorShift128+ (an LFSR-based PRNG at 0.48 cycles per byte on Kaby Lake).


Factoring a 512-bit number? I want to know how to factor this number only given $n$ and $e$, I have tried to factorize $n$ using Fermat's little theorem and also tried primefac module in python (running for the past 4 days) but had no luck, and I want to know how $n$ can be factorized.
For the values follow this link: https://pastebin.com/37WFzBvm

Your best bet is running the General Number Field sieve (implemented by e.g. CADO-NFS or msieve) on a bunch of beefy computers. The GNFS is the only algorithm to have ever been used to factor 512-bit integers and in fact there is an open-source script (collection) Factoring-as-a-Service that will automatically factor a given number using AWS EC2 for about 100USD (in 2015, now it can probably be adjusted to use newer, faster instances which are cheaper).

Of course using the GNFS should always stay the last resort option. What you have tried so far (without luck it seems):

An optimized variant of Pollard-Rho, which finds small factors quite fast.
An optimized variant of the quadratic sieve (single-threaded), which brute-force-factors numbers up to about 250-300 bit faster than the GNFS.
Pollard p-1 and William's p+1 factoring which work quite well if either of p-1 or p+1 has a smooth factorization
The Elliptic Curve Method (ECM) which should find small factors up to about 200 bit (larger if more time).

What I could still imagine to maybe work is some Fermat-Factoring or maybe the Special Number field sieve.
But then, the proper strategy probably depends on the context in which you encountered this. If it was during e.g. a security review and you want to demonstrate the insecurity, then the GNFS is probably the way to go, if you encountered this during some homework, then some algorithm you learned prior is probably the way to go.


Security of (2,2) Shamir's visual secret sharing scheme : How are the 2 shares random? From the Visual Cryptography by Shamir and Noar.

Let us take the pixel expansion as 2. Therefore, each pixel will be represented by 2 pixels (also called as subpixels) in a share. Since this is a (2,2) scheme, we will have 2 shares. In order to create share1 for a white pixel, a fair coin is tossed with 2 possibilities of subpixels - Black&White or White&Black - either one of these 2 choices is chosen to represent a white pixel. It is clear that Share1 is random.

In order to create share2 for a white pixel, is a coin tossed again?
If yes, then how is reconstruction of a white pixel assured?
If no, then how is share2 random?
Assuming that in the reconstructed image, the white pixel will be 50% black and 50% white.

First of all, coin tossing represents a uniform random generator. Therefore, the selections are assumed to be uniform.

In order to create a share for a pixel, as you mentioned, a pixel split into two subpixels. A share for

a white pixel can be $[(B|W),(B|W)]$ or $[(W|B),(W|B)]$
a black pixel can be $[(B|W),(W|B)]$ or $[(W|B),(B|W)]$, where in $[(x,y)]$, $x$ represents the color of left pixel and $y$ represents the color of right pixel.

or, one can see from the image;

The superposition is putting the images on top of each other. White shares construct a half white and half black square and black shares construct a black square. When the selection is random, the shares are indistinguishable from being white or black.

How a share is constructed

For each pixel, toss a coin to select a row. For example, assuming that when the toss result is Tail, we select the first rows;

for white pixels, select $[(B|W),(B|W)]$ and
for black pixels, select $[(B|W),(W|B)]$.

Similarly, for Head result, we select the second rows.

for white pixels, select $[(W|B),(W|B)]$ and
for black pixels, select $[(W|B),(B|W)]$.

The confusion

If we toss a coin for the second share (instead of selecting the share together), then for example; for a white pixel after a Tail (select first row $(B|W)$), we may select the second row with a Head then the white pixel will be shared as $(B|W)$ and $(W|B)$. In superposition, however, this constructs a black pixel $(B,B)$. Therefore, they must be selected together.

Share 1 and share 2 are random in group-wise.


Bit commitment, two blobs with same bit, without revealing it? Suppose we have bit commitment scheme:
$n=p*q$ and $t \in QNR_n$, with Jacobi $(\frac{t}{n})=1$

Commitment(P), random $x\in \mathbb{Z}_n$, $y=x^2t^b$, where $b$ is bit.

Ok, suppose we have $y_1$ and $y_2$ blobs containing same $b$

How P can prove that both blobs contain same bit without revealing it?

Give a zero-knowledge proof that $y_1 \times y_2$ is a Quadratic Residue.

[Extra verbage included because a one line answer feels too brief]

If we have $y_1 = x_1^2 t^{b_1}$ and $y_2 = x_2^2 t^{b_2}$, then $y_1 y_2 = (x_1x_2)^2 t^{b_1 + b_2}$.

If $b_1 = b_2$, this product is either $(x_1x_2)^2$ (if $b_1 = b_2 = 0$), or $(x_1x_2t)^2$ (if $b_1 = b_2 = 1$), in both cases a Quadratic Residue.

If $b_1 \ne b_2$, this product is $(x_1x_2)^2 t$, which is a Quadratic Nonresidue, hence we would not be able to generate a Zero Knowledge Proof that it is.


Hash function as secure as one-time pad? We know that the one-time pad is provably secure as a cipher to encrypt some data. Is there an algorithm which does the same just as a hash function? Can we get a provably secure hash function? Maybe with some ridiculous properties like the one-time pad got them (really big key length, fully random key)?

OTP requires 1) random key material as long as the message to be encrypted 2) no reuse of the key material or any part, ever 3) secure transmission of the key material between communicants 4) no key material becomes known to anyone ever.
And even then, OTP only guarantees that no other encryption will be harder to break. NOT that a message can't ever be recovered.

1) random -- for crypto purposes, random is very very hard, and very very tricky. We don't know how to do it, though we think some schemes are pretty good. There are many tests, but there are more ways to be non-random than there can be tests.

2) no reuse -- reuse makes an OTP worthless. The Russians did a little reuse in WWII and NSA was eventually able to read some of the traffic encrypted with reused key material. See Venona Project.

3) secure transmission -- NO ONE has solved the secure transmission of arbitrarily long material between nodes. There are Xerox machines, disk copiers, thumb drive copiers, ... Plus burglary (which can sometimes be covered up, leaving the sender making a very bad and completely insecure assumption),

4) no exposure of key material ever -- this requires a degree of fail safe control of the security of stuff well into the future. Humans aren't really compatible with this sort of thing.

But, good hash algorithms (and we are not SURE any of ours are good enough, there's been a poor track record) can be claimed to produce an unpredictable (and so random) string when fed with a suitable input. Sadly, they are deterministic.  Feed a hash algorithm abcd... more than once and you'll get out the same hash. Which means that the unpredictability of hash algorithms is dependent on unpredictability in their inputs.  Not a good thing, people being people. But, if you use some CSRNG for the inputs, why bother with the hash algorithm? If the CSRNG is defective, so will be the randomness of the hashes you produce.

But even if you, foolishly, hand wave away these issues, nearly all hash algorithms produce a shortish bit string.  Say, 128 bits, or 256, or some such. So you could send a message, using one of these hashes as the OTP key material, 128 or 256 bits long.

I wouldn't bother in practice, and wouldn't touch it with a ten foot pole for a theoretical study.  Too much contingency, too much dependence on things athat are out of anyone's control, ....