Summer project HW
HW1
classic cryptography and modern arithmatic
1) You are given a ciphertext encrypted under Caesar cipher: “ibbiks eqbp nctt nwzkm ia awwv ia bpm acv zqama”. Recover the key and the plaintext.
ibbiks eqbp nctt nwzkm ia awww ia bpm acv zqama
key=8
plaintext: attack with full force as soon as the sun rises
2) Ceasar cipher: suppose that Alice and Bob generates three keys and uses triple encryption. That is, they encrypt the message using the first key, then encrypt the result using the 2nd key, then encrypt the result again using the 3rd key using a Ceasar cipher. Is this secure? Show a way to break it.
It is not security: the difference between one keys is the change steps about each letter,so we can use the same way to break it.
the solution is brute force attack:Firstly,we should get the ciphertext.secondly,we try all the possible keys, and see whether the possible plaintext make sense.
3) Compute 3292213^41 mod 100. How many multiplications did you require? How many digits did the numbers (which you had to multiply) had? Try to make it as efficient as you can.
3292213 mod 100=13
13^2 mod 100 =3292213^2 mod 100=69
69^2 mod 100=3292213^4 mod 100=61
61^2 mod 100=3292213^8 mod 100=21
21^2 mod 100=3292213^16 mod 100=41
41^2 mod 100=3292213^32 mod 100=81
hence:41 = 32+8+1
3292213^41 mod 100=（81 * 21 * 13）mod 100=13
8 Multiplication.
digits: 2
4) Compute Discrete log of y=6 with respect to base g = 5 and modulas N = 7.
brutal force：
5^1 mod 7=5
5^2 mod 7=4
5^3 mod 7=6
x=3
5) (no need to submit): Read and understand notions of digital signatures, public key encryption, and key exchange. Understand the differences between these.
digital signature use the private key to encrypt the message，and form a signauture. the other person use public key and message and signature to verify the message is sended by correct person.
The proecess is similar to an inverse process about Encrypted communication.
HW2
OTP and Digital signature
1) Alice and Bob want to write encrypted messages in an e-diary. They agree on the following convention: (1) all messages of Alice will start with n 0s, whereas (2) all messages of Bob will end with n 0s. Thus, if Alice wants to write a message m, she will encrypt the message 0^n || m (where 0^n is a string of n 0s, and || denotes concatenation).
Likewise, Bob’s messages will be of the form m || 0^n. Assume that the actual message m is also of length n and m is not equal to 0^n. Note that with this encoding, each string that Alice and Bob write in the diary is of length 2n. To encrypt the message, Alice and Bob agree to use one-time pad and jointly select a random key k of length 2n which they will use to encrypt and write their strings to the diary.
Show that this scheme is completely insecure. In particular, show how to recover the key k completely.
For one time pad, the key can’t be reused .
The attacker can get the ciphertexts sent by Alice and Bob to each other.
Alice write a message m1, she encrypt the message 0^n || m1, mark the 0^n as M1.Then:C1=M1⊕ K1 . The attacker know the so the Key can be calculate：K1=C1⊕M1.In this way, we can get the first half of the Key.
Similary,Bob write a message m2 to Alice, he encrypt the message m2||0^n. Then：C2=M2⊕ K2.Hence：K2=C2⊕ M2.K2 is the second half of the Key.
So we get the K combinated with K1 and K2.
For example:
n=6 ,MA=000000XXXXXX, MB=XXXXXX000000 , C1=101101001011, C2=001011110010
Then:K1=101101 K2=110010 K=101101110010
C1⊕ C2=100110111001,MA=000000111001 ,MB=100110000000
TA’s answer: We observe the property of one-time pad: if you encrypt an all 0 string, then the ciphertext is equal to the key itself. This is because XORing with 0 doesn’t change any string.
With this observation, if the first n bits of Alice’s message are 0, then the first n bits of the ciphertext will be equal to the first n bits of the key. This allows an attacker to recover the first n bits of the key by looking at the ciphertext written by Alice.
Similarly, by looking at the ciphertext written by Bob, the adversary can recover the last n bits of the key. Now the adversary has the full key and can decrypt anything.
2) Alice and Bob would like to communicate securely. Each day, Alice will send exactly one message to Bob: “ATTACK” or “DEFEND”. An adversary should not be able to change the message which Alice sends to Bob. Neither should the adversary be able to see it. Describe a solution which would work. You can assume all cryptographic objects which we have studied so far.
(1)One method is using HTTPS to communicate with each other, but one side maybe ask the third party certification authority for CA.
还要使用时间戳防止重放攻击。
(2)sign firstly and then encrypt and lastly sign . Use one time signature to sign and asymmetric encryption to encrypt.Double signature can avoid adversary tampering with identity，and encryption can avoid adversary see the message.
Firstly, use SK sign message as S .
Secondly, use public key encrypt S and M as C.
Thirdly, receiver use private key decrypt C.
Fourthly,reuse SK sign C as S’ ,and send S’ to the receiver.
TA’s answer:HTTPS and digital signature
Simply use an encryption scheme (like one-time pad) to hide the message. To ensure that the adversary can’t change it, use digital signatures. So Alice and Bob meet first and share keys for one-time pad. In addition, Alice stores Bob’s digital signature verification key and Bob stores Alice’s. Then if Alice wants to send a message to Bob, she would encrypt it first and then sign the ciphertext and send it across. Bob can can do the same. Note that using encryption scheme alone is not secure. For example, in one-time pads, if you change the first bit of the ciphertext, it changes the first bit of the plaintext (even though you don’t know what the first bit is).
3) We used the XOR gate for one-time pads. Could we have used AND gate or OR gate? Why or why not?
No.
For AND:If C=0,K=0, then M=1 or M=0, so we can’t decrypt cipher text.
Similarly:If C=1,K=1,then M=1 or M=0,so we can’t decrypt cipher text.
Instead, use the XOR gate, can be uniquely determined.
encrypt：C=M⊕K
decrypt：M=C⊕K
What’s more, for AND:If C=1,then the K=1 and M=1.we can get unique M and K.Similarly for OR gate, If C=0 then the K=0 and M=0.
So can’t use AND gate and OR gate for one-time pads.
TA’s answer:AND and OR do not lead to secure one-time pad. If we are using AND, then if we see a 1 in the ciphertext, we know that bit of the key must be 1 and that bit of the message must be 1. Similarly for OR, if we see a 0 in the ciphertext, we know that that bit of the key as well as the message must be 0. So security doesn’t hold. In fact, it may not even be possible to decrypt the message properly even if you have the correct key. This is because for example, if we are using AND and the key is 0, the ciphertext will always be 0 and regardless of what the message is. In this case, you can’t recover the message from the ciphertext.
Does it really matter if we used AND, OR or XOR with the one-time pad? The answer is yes, and it’s extremely important to understand why. AND has a 75% chance of outputting 0 and a 25% chance of outputting a 1. While OR has a 25% chance of outputting 0 and 75% chance of outputting 1. While the XOR operation has a 50% chance of outputting 0 or 1.
https://www.khanacademy.org/computing/computer-science/cryptography/ciphers/a/xor-and-the-one-time-pad
4) Alice proposes a one-way function f(x) = 2x^2 + 5x + 3. Is this a secure one-way function?
Hint: read about solving quadratic equation
It is not a secure one-way function.
Every x∈（－∞，－５/４）∪（－５/４，＋∞）,there exists a x’ , where x’=x and f(x’)=f(x) .
What’s more , there is Vieta formula to solve quadratic equation, so it is easy to find x.
To sum up ,it is not a secure one-way function.
TA’s answer:This is not secure because given 2x^2 + 5x + 3, it is easy to compute x. Please read about solving quadratic equations. There is a simple formula to solve for x.
5) Recall that even if the server only stores f(p), client has to send p in clear to authenticate to the server. If the adversary is watching, it learns p. Normally you have to use HTTPS to solve this problem. Alice has another idea. Instead of client sending p, client will instead only send f(p) to the server to authenticate. Then the adversary never learns p even if it can watch the whole communication. Is this a good idea? Does it improve the security of the system?
No, Adversary can bypass encryption process and send the f(p) to the server for authentication.In some extend, it is equal to no encryption.
TA’s answer:This is not a good idea.If the client only needs to send f(p) to the server to authenticate rather than using p, anyone with the knowledge of f(p) is able to communicate with the server and he no longer needs the information of p. However, an adversary can learn f(p) in this situation.
6) Consider the one-time digital signature scheme discussed in the lecture. Suppose the adversary can get signatures on any two messages of his choice. Show how the adversary can produce a signature on a third message (different from the first two).
Make the message length in the first two times is same as the message length in the third time.
First time , sent message 0^n(e.g 0000) and then get signature X0(vector with length n).Second time ,sent message 1^n(e.g 1111) and then get signature X1(vector with length n).Then we can get corresponding signature for 0 and 1 for every bits.So we can produce a signature on a third message.
if m[i]=0, σ[i]=x0[i] and if m[i]=1, σ[i]=x1[i] (1<=i<=n)
For example , a third message is 1011, then the signature is (X1[1],X0[2],X1[3],X1[4])
TA’s answer:Here is the one-time digital signature scheme.
If the adversary can get signatures on any two messages, he or she can then choose one message that contains only 0s and another message containing only 1s. In that case, the adversary will know the signature corresponds to the message in which every bit is 0, and the signature corresponds to the message in which every bit is 1, so that he’ll be able to sort out the entire correspondence, and generate the signature on a third message with contents that can be freely selected, making the system totally insecure.
HW3
Block chain
Q1: Consider the hash function H used for Bitcoin mining. Suppose this function has the property that its possible to find collisions. In other words, for any string s1, its possible to find another string s2 (even with certain patterns) such that H(s1) = H(s2) in about 10 hours. Show that this will lead to problems in Bitcoin security.
Answer1：Because i-th block has the hash value of (i-1)-th block, then one hash value two corresponding values, so there will be two answers when we find the (i-1)-th block.
In the bitcoin transaction, we can change the transaction information , but the verification passed.
TA‘ answer：Bitcoin security will break down in this case. This is because if the adversary can find another Block which has the same hash, then adversary can change that block and put the new one instead of that in the Blockchain. This attack cannot be detected because the hash will remain the same.
Q2: Suppose an adversary has found an algorithm to forge digital signatures used in Bitcoin.
That is, adversary can sign arbitrary message without having your signing key.
1）Assume you are constantly monitoring the blockchain. Can the adversary steal your Bitcoins without you being able to detect?
Adversary can’t do it.Because the transaction information are broadcasted to public, so you can detect when your Bitcoins are stolen.
2）Come up with a strategy for the adversary to steal your Bitcoins so that there is no way for you to get them back (assuming you cannot forge signatures).
Adversary sign a bitcoin exchange message, which send bitcoin to designated account such as the adversary‘s account. This process is irreversible and cannot forge signatures.
TA‘ answer： A: 1) No, the adversary has to broadcast the transaction which steals your Bitcoins. This transaction must appear on the Blockchain. So you will be able to detect it. However even if you detect it, its not clear how to stop it. 2) Adversary can simply transfer all you coins to another public key which he owns. Then there is no way for you to get them back.
Q3: Bob has an idea to make Bitcoin more green and environmental friendly. Rather than wasting computational resources and electricity on solving a meaningless hash puzzle, why not solve a puzzle which is good for the society? Bob proposes that miners compete to solve hard problems in DNA sequencing. The person who mines the current block will also pick a DNA sequencing problem the next miner must solve in order to mine the next block. Is this secure?
Note: you don’t need to understand what DNA sequencing is. Just think of them as some large computation scientists need to perform to understand human genes better.
It is not security.
（1）The person who mines the current block will also pick a DNA sequencing problem the next miner must solve, so the person maybe choose the DNA sequencing problem he has known the answer, then there is little probility for others to mine the block successfully.
（2）If use DNA sequencing, there will be some people who steal other‘s answer to get reward.Instead, when we solve the hard problem, we should slove the H(Bi-1||ti||pk||r)=000( k times)……There has pk to identify the miner, so it is hard to steal answer.
A：This is completely insecure. This is because the person who mines the current block can just pick a puzzle whose solution he already knows. Then the same person will be able to mine the next block as well. This process can continue and a single miner can take over the entire system.
Q4: Suppose that there are two forks in Bitcoin. Is it possible that both of them will be equally long and will continue to be equally long? Please explain your answer.
I think it is not possible.
The probability of finding the answer at the same time is little, so continuing to be equally long is scarcely possible.
A: No. Mining of blocks is a randomized process. Hence, sooner or later, one fork will become longer than the other. As soon as that happens, all (honest) miners will switch to that fork and the other fork will be left further and further behind.
Q5 (Selfish Mining Attacks): Alice is successful in mining the i-th Bitcoin block. Rather than broadcasting the block (and the puzzle solution) to everyone over the network, she decides to keep it to herself and continue mining further blocks on it. Indeed, if she broadcasts the i-th block and the puzzle solution to everyone, this is only going to increase competition for mining the (i+1)-th block. Since she is ahead of everybody at this point, her idea is to continue mining on it, get a couple more blocks, and then broadcast all these blocks at the same time to lock-in rewards for a few blocks (rather than a single block). Suppose Alice control only 10 percent of the computing power. Is this the right strategy for her? Why or why not?
It is not the right strategy for her.
Because she only control 10 percent of the computing power, so there is great possiblity that other people mining the i-th Bitcoin block while Alice is mining the (i+1)-th block.
A: No, by doing that, Alice risks losing reward even for the current block. Since other miners have a lot more computing power than Alice, it is very likely that they can mine both block i and block i+1 before Alice can mine Block i+1. If that happens, Alice loses the reward even for Block i.
6) Suppose someone gives you an algorithm to solve the CDH problem: it takes as input g, g^a, g^b and output g^ab. Show how you can use this to break Elgamal encryption.
Firstly, get the g^a,g,g^b and C(CipherText).
Secondly, get the g^ab by the algorithm, the g^ab is the key. K=g^(ab)
Thirdly,use extended euclidean algorithm to solve K, M=C*k^(-1)
A:Adversary knows g^a since that is the public key. g^b is part of the ciphertext. Using the given algorithm, adversary can compute g^ab. Now given M.g^ab, adversary can easily compute M by computing the inverse of g^ab and multiplying with M.g^ab.
7) Consider auctions done using ElGamal Encryption. Alice is selling a Phone and has public key PK. Bob would like to Bid 100 dollars. He encrypts his bid under public key PK and sends it to Alice. Trudy is watching over the channel and sees the ciphertext. He doesn’t know Bob’s bid. But he would like to bid exactly double of Bob and win the auction in style. Show that this is possible in ElGamal encryption.
Trudy sends his ciphertext twice as much as the Bob’s.
For example, Bob:C=MK and Trudy: C’=2M*K
A: Here Trudy can indeed win. ElGamal ciphertext is g^b, M.g^ab. Using this, Trudy cannot recover M. But Trudy can multiply M.g^ab by 2. Trudy can then send g^b, 2.M.g^ab to Alice. When Alice decrypt this, Alice will get 2M.
HW4
RSA
Q1: Consider auctions done using textbook RSA Encryption. Alice is selling a Phone and has public key PK. Bob would like to Bid 100 dollars. He encrypts his bid under public key PK and sends it to Alice. Trudy is watching over the channel and sees the ciphertext. He doesn’t know Bob’s bid. But he would like to bid exactly double of Bob and win the auction in style. Show that this is possible in RSA encryption.
Note: textbook RSA means without using hash
Bob:C=M^E mod N
so Trudy: C’=M^E * (2^E) mod N = (2*M)^E mod N
Because we know the public key E, so we can multiply C by 2^E.
—–这叫做密文的可构造性（malleable）
A: RSA ciphertext is C = M^e mod N. Using this, Trudy cannot recover M without the knowledge of d. But Trudy can compute C‘ = 2^e mod N. Then Trudy computes C.C’ = (M^e).(2^e) mod N = (2M)^e mod N. Now Trudy can send (2M)^e mod N to Alice. When Alice decrypts this, she will get 2M.
Q2: We saw that textbook RSA signatures are not secure because you can multiply two different signatures to obtain new signatures on new messages. However is textbook RSA at least a one-time signature scheme? That is, suppose that the adversary only gets a signature on a SINGLE message m. Can the adversary produce a signature on a different message m’ not equal to m?
Yes. For example, c=m^E mod N c’=(m* m)^E mod N . Therefore, we can signature on a different message m’=m * m not equal to m.
A：No, textbook RSA is not even one-time secure. Given a signature s = M^d mod N on message M, adversary can just compute s. s = (M^e). (M^e) mod N which will be (M^2)^e mod N. This is a valid signature on message M^2.
Q3: Consider the following variant of the ElGamal commitment scheme we saw in the class. The committer chooses a,b and sends g, m.g^ab to the receiver (where m is the message to be committed). In the opening phase, the committer sends a, b to the receiver. The receiver computes g^ab and then recovers the message. Is this commitment scheme binding? Is this hiding? Please give brief 2-3 line arguments.
This commitment is hiding not binding.
(1) Given g and m*g^(ab) is less than original parameters, so it is hiding.
(2) If the committer is dishonest: For example, if C=M * g^(32)，but committer can send a=4，b=5 to receiver. so the C=M’ * g^(45). And M’ is not equal to M. Therefore, the commitment is not binding.
A：Hiding: This is because the committer can send any a, b during the opening phase. Different values of a, b will lead to different values of g^ab. This is turn will lead to different values of the message M. Not Binding: This is because compared to the Elgamal commitment scheme, the receiver gets even less information in the commitment phase.
Q4: Consider the following protocol for 2-party coin flipping. First, Alice commit to her bit b0. Then Bob commits to his bit b1. Then Alice opens b0 following which Bob opens b1. The output is the XOR of these two bits. Is this secure?
This is not secure.
Bob can copy Alice’s commitment, then the b1=b0, so b=b0 XOR b1=b0 XOR b0.This is a decisive result. So it is not secure.
A: This is not secure. Bob can just replay the same commitment which he received from Alice. Then b1 = b0 and XOR is always 0. Hence, Bob can make sure that the outcome of coin flipping is always 0.
HW5
ZK proof
Q1: Consider the ZK proof for graph 3-coloring. What if the prover doesn’t permute the colors in every iteration? That is, the prover permutes the colors once in the beginning and then sticks to that permutation for all iterations. Will the protocol still be zero-knowledge?
No, it cannot satisfy the zero-knowledge property.
If not permutes the colors, Verifier will know the knowledge after several steps. It is not satisfy the zero-knowledge property.
Q2: Consider the MPC protocol which we just saw. Suppose that the first and third student are colluding. Show that they can compute the age of the second student.
Say the first student and the third student know P1 and P3 separately, the age of third student is A3.
So the age of the second student is A2=P3-P1-A3.
Quiz
1) Alice and Bob have an idea to make one-time pad even more secure. They generate two keys for one-time pad and use double encryption. That is, they encrypt the message using the first key, then encrypt the result using the 2nd key. Is this more secure than using just a single key? Explain your answer.
No.it is same as the secure of a single key.
C=M XOR K1 XOR K2 = M XOR K (If the K=K1 XOR K2)
C’=M XOR K3
There is no big difference between two encryption method. We can just use K directly to encryption M, so it is not more secure than using just a single key.
2) In bitcoin, typically takes 10 minutes to 1 hour to confirm the transaction. Alice needs to pay Bob and has an idea to make the transactions instantaneous. Instead of sending the transactions to the miners, Alice directly sends the signed transaction to Bob. Bob checks the signature from Alice and checks if Alice has enough coins for this payment. If so, Bob gives the product to Alice. And then Bob broadcasts the transaction over the Bitcoin network. Miners can then take their own time and include this transaction in the public ledger. Is this safe for Bob?
It is not secure for Bob.
There may be double spending attack. For example, Alice trade with other people using same money.In the meanwhile, two miner mined successful and record two different transactions into the block separately. There are forking. When the blockchain which record Bob’s profit is shorter than the other, then the trasaction between Bob and Alice will be invalid.
3) Design a multiplicatively homomorphic encryption scheme. This mean, given an encryption of a and encryption of b, you should be able to compute an encryption of a.b without having access to the decryption key.
Hint: check all the encryption schemes which we covered in class and see if any of them have this property.
RSA encryption.
Enc(a)=a^E mod N
Enc(b)=b^E mod N
Enc(a * b)=(a*b)^E mod N=Enc(a) *Enc(b)