1) Number Theory
a)
First note that since 17 is prime,
j(17) = 16. Then:
32007 mod 17 = 32007 mod 16 mod 17 = 37
mod 17 = 11 mod 17.
b)
We list the numbers in pairs (I, J): (1, 1), (2,9), (3, 6), (4, 13), (5, 7), (8,15),
(10, 12), (11, 14), (16, 16).
C) Fix an I. Now,
consider I * J for each J in S(n). Observe that I * J
also lies
in the set S(n). Further observe that I * J is
different for each J, since I * J1
= I * J2 mod n implies I * (J1 – J2) = 0 mod n which implies J1 = J2.
Hence I *J takes on every value in S(n) and in
particular the value 1 since
1 is in S(n). Thus there exists an I such that I
* J = 1 mod n.
d) 38 = 9 mod 14.
x = 9.
Exponentiation is easier to compute since we can do repeated squaring.
Discrete log is harder to compute because the best way (we know as of
today) is to try all possibilities using brute force.
2) RSA & Diffie-Hellman
a)
In
RSA a person picks two large random primes, p, q, and forms their product n =
pq. Then the person finds
d and e such that de = 1 mod j(n), where j(n) =(p-1)(q-1). The person’s public key is <e,n> and the person’s private key is <d>. To encrypt a message m the person
computes me mod n. To
decrypt the cipher text c the person
computes cd mod n. Observe that (me)d mod n = mde mod n = m mod n because de = 1 mod j(n).
b) To sign a message m the person generates
<m, md mod n>. This signature
can be easily verified by checking that (md)e mod n =
m mod n.
c) First, 3
values are selected <p,g,T>. These are publicly
known, in fact,
they have to be “published” in a trusted place to prevent
“man-in-the-
middle attack. p is the prime number
(additionally it is better for it to be a
‘safe prime’, when (p-1)/2 is
also a prime). g is a generator and T is the
public key, T=gS mod p, where S is the private key.
When the two nodes A and B want to communicate they make <p,g,TA> and <p,g,TB> known to each other and node A computes (TB mod p)A mod p = gBA mod p, node B computes (TA mod p)B mod p =gBA mod p =gAB mod p. Thus the shared key is gAB mod p. Since the problem of discrete log is not solvable at this time, knowing only gA and gB, nobody else can compute gBA without knowing A’s and B’s private keys. To send a message m to B, A sends c = m * gBA mod p. To decrypt and recover m B computes c/ gBA mod p.
d) If the same R is used for two different messages, M1 and M2 then it becomes possible for an attacker to easily recover
S = ((R + M1 * S) – (R + M2 * S))/(M1 – M2) mod (p – 1).
3) Crypto systems and network protocols
a)
112-bit 3DES is much stronger than 112-bit RSA. A brute-force attack
would require searching a key-space of 2112 keys for 112-bit DES.
However, for asymmetric encryption algorithms like RSA not all 112-bit binary
strings have to be considered, since an RSA key is the product of two large
prime numbers. Thus an attacker can limit the search only to binary sequences
that represent the product of two large prime numbers.
b) The handshake consists of 4
steps.
1. Host A initiates a connection
saying:
It wants to talk.
The ciphers it supports (RSA, DES,
etc)
A random number R1
2. Host B replies
with:
A Certificate
A Session ID
The cipher it chooses
A random number R2
3.
Host A responds with:
{S}KB i.e. S encrypted using B’s public key
Hash of 1, 2, and K
4.
Host B responds with:
Hash of 1, 2, and K
c) From the handshake in part a) it is clear that a secret key can be established without needing a public/private key pair for the client. The public key of the server is sufficient for the handshake and establishment of the secret key. Hence the client does not need its own keys. However if client side certificates are used as a means of authentication then of course the client needs a public/private pair.
4)
SSL C Client source:
/*
Compile
command:
gcc openssl_client.c -Wall
-L/arch/unix/lib/ -I/arch/unix/include/ -lssl -lssl -lcrypto
-lsocket -lnsl -lresolv -o
openssl_client
*/
#define
OPENSSL_NO_KRB5
#include
<openssl/ssl.h>
#include
<openssl/err.h>
#include
<sys/types.h>
#include
<sys/socket.h>
#include
<netinet/in.h>
#include
<sys/socket.h>
#include
<netinet/in.h>
#include
<arpa/inet.h>
#include
<string.h>
#define
DUMP_SSL_ERR() { fprintf(stderr, "Error %s:%d -\n", __FILE__,__LINE__); ERR_print_errors_fp(stderr);
}
#define
DUMP_SSL_ERR_EXIT() { DUMP_SSL_ERR(); exit(1);
}
int main(int argc, char **argv)
{
int
port;
char *line, *host;
char buff[1024];
int fd;
SSL_CTX *sslctx;
SSL
*ssl;
struct sockaddr_in saddr;
if (argc<4)
{
fprintf(stderr, "Usage: %s <host (ip only)> <port> <line>\n", argv[0]);
return 1;
}
host=argv[1];
port=atoi(argv[2]);
line=argv[3];
SSL_load_error_strings();
SSL_library_init();
sslctx=SSL_CTX_new(SSLv23_client_method());
if (!sslctx)
DUMP_SSL_ERR_EXIT();
fd=socket(PF_INET, SOCK_STREAM,
IPPROTO_TCP);
if (fd==-1) { perror("socket"); exit(1); }
saddr.sin_addr.s_addr=inet_addr(host);
saddr.sin_family=PF_INET;
saddr.sin_port=htons(port);
if (connect(fd, (struct sockaddr *)&saddr, sizeof(saddr))==-1) {
perror("connect");
exit(1);
}
/*
Create a new SSL instance and connect over the existing
socket */
/*
send your hashed line and read the output and ensure it is a 0 for success
*/
ssl=SSL_new(sslctx);
if (!ssl) {
DUMP_SSL_ERR(); exit(1); }
if (!SSL_set_fd(ssl, fd)) { DUMP_SSL_ERR();
exit(1); }
SSL_set_connect_state(ssl);
if (SSL_connect(ssl)!=1) { DUMP_SSL_ERR(); exit(1); }
if (!SSL_write(ssl, line, strlen(line)))
{
DUMP_SSL_ERR();
exit(1);
}
if (!SSL_write(ssl, "\n", 1)) {
DUMP_SSL_ERR();
exit(1);
}
if (!SSL_read(ssl, buff, sizeof(buff)))
{
DUMP_SSL_ERR();
exit(1);
}
printf("read %s\n", buff);
return 0;
}
SSL Java Client source:
import javax.net.ssl.*;
import javax.net.*;
import java.net.*;
public class SSLClient {
public static void main(String[] args) {
SSLContext
sc;
/* Trust all certificates
without verifications */
/*
http://javaalmanac.com/egs/javax.net.ssl/TrustAll.html */
TrustManager[] trustAllCerts =
new TrustManager[] { new
X509TrustManager() {
public java.security.cert.X509Certificate[]
getAcceptedIssuers() { return
null;
}
public void checkClientTrusted(
java.security.cert.X509Certificate[] certs, String authType)
{
}
public void checkServerTrusted(
java.security.cert.X509Certificate[] certs, String authType)
{
}
}
};
try
{
sc = SSLContext.getInstance("SSL");
sc.init(null, trustAllCerts, new java.security.SecureRandom());
} catch (Exception e)
{
e.printStackTrace();
return;
}
SocketFactory factory = sc.getSocketFactory();
/* YOUR CODE HERE
*/
/* Connect to the server over an SSLsocket and send your hashed line */
/* Read the output and
ensure it is a 0 for success */
try
{
SSLSocket s = (SSLSocket) factory.createSocket();
s.connect(new InetSocketAddress("127.0.0.1", 12345)); s.getOutputStream().write("ravi:5f7c7331d5f3477de04a823db9042cee\n".getBytes());
byte[] ret = new
byte[1024];
s.getInputStream().read(ret);
String retstr = new String(ret);
System.out.println(retstr);
} catch (Exception e)
{
e.printStackTrace();
return;
}
}