RSA: Public-Private Key

The other night whilst bored I decided to get some knowledge of how public/private keys work.

The idea that something can be encrypted with one number that is public, but decrypted with another that is private seems a bit weird, but it works.

Using the wiki article on RSA, I implemented an key generator and encoder/decoder, but I haven’t gotten much closer to understanding why it works.

#include <stdint.h>
#include <stdio.h>
 
//
struct Key
{
	uint64_t mod;
	uint64_t exp;
};
 
//
void GeneratePublicPrivateKeys(Key & outPublicKey, Key & outPrivateKey);
uint64_t Encrypt(const uint64_t inSource, const Key & inKey);
uint64_t Decrypt(const uint64_t inSource, const Key & inKey);
 
//
int main(int argc, const char * argv[])
{
	const char str[] = "This is a test";
	Key publicKey;
	Key privateKey;
 
	//
	GeneratePublicPrivateKeys(publicKey, privateKey);
 
	//
	printf("Message    Encrypt    Decrypt\n");
	{
		for(uint64_t i = 0; i < 256; ++i)
		{
			uint64_t c = Encrypt(i, publicKey);
			printf("%7llu%11llu%11llu\n", i, c, Decrypt(c, privateKey));
		}
	}
	printf("\n");
 
	//
	uint64_t encoded[sizeof(str)];
 
	printf("Encoded Message: \n");
	{
		for(int i = 0; i < sizeof(str); ++i)
		{
			encoded[i] = Encrypt(str[i], publicKey);
 
			printf("\t%d > %llu\n", str[i], encoded[i]);
		}
	}
	printf("%s\n\n", str);
 
	//
	char decoded[sizeof(str)];
 
	printf("Decoded Message: \n");
	{
		for(int i = 0; i < sizeof(str); ++i)
		{
			decoded[i] = Decrypt(encoded[i], privateKey);
 
			printf("\t%llu > %d\n", encoded[i], decoded[i]);
		}
	}
	printf("%s\n", decoded);
 
	return 0;
}
 
// https://gist.github.com/cslarsen/1635288
uint64_t totient(uint64_t n)
{
	if(n == 1)
	{
		return 1ll;
	}
 
	uint64_t out = n;
 
	// 2
	if(n % 2 == 0)
	{
		out -= out / 2;
		do
		{
			n /= 2;
		}
		while (n % 2 == 0);
	}
 
	// odds
	for(uint64_t i = 3; i * i <= n; i += 2)
	{
		if(n % i == 0)
		{
			out -= out / i;
			do
			{
				n /= i;
			}
			while(n % i == 0);
		}
	}
 
	//
	if(n > 1)
	{
		out -= out / n;
	}
 
	return out;
}
 
// http://www.math.wustl.edu/~victor/mfmm/compaa/gcd.c
uint64_t gcd(uint64_t a, uint64_t b)
{
	int64_t c;
 
	while(a != 0)
	{
		c = a;
		a = b % a;
		b = c;
	}
 
	return b;
}
 
// http://rosettacode.org/wiki/Modular_inverse#C.2B.2B
uint64_t modinv(uint64_t a, uint64_t b)
{
	int64_t b0 = b, t, q;
	int64_t x0 = 0, x1 = 1;
 
	if(b == 1)
	{
		return 1;
	}
 
	while(a > 1)
	{
		q = a / b;
		t = b, b = a % b, a = t;
		t = x0, x0 = x1 - q * x0, x1 = t;
	}
 
	if(x1 < 0)
	{
		x1 += b0;
	}
 
	return x1;
}
 
// http://stackoverflow.com/questions/8496182/calculating-powa-b-mod-n
uint64_t modpow(uint64_t base, uint64_t exp, uint64_t modulus)
{
	base %= modulus;
	uint64_t result = 1;
 
	while(exp > 0)
	{
		if(exp & 1)
		{
			result = (result * base) % modulus;
		}
 
		base = (base * base) % modulus;
		exp >>= 1;
	}
 
	return result;
}
 
//
void GeneratePublicPrivateKeys(Key & outPublicKey, Key & outPrivateKey)
{
	const uint64_t p = 17; // random prime number
	const uint64_t q = 19; // random prime number
	const uint64_t n = p * q;
 
	int64_t phi = totient(n);
	int64_t e = 0;
 
	for(int64_t i = 3; i < phi; ++i)
	{
		if(gcd(i, phi) == 1)
		{
			e = i;
			break;
		}
	}
 
	int64_t d = modinv(e, phi);
 
	// Public Key
	outPublicKey.mod = n;
	outPublicKey.exp = e;
 
	// Private Key
	outPrivateKey.mod = n;
	outPrivateKey.exp = d;
}
 
//
uint64_t Encrypt(const uint64_t inSource, const Key & inKey)
{
	return modpow(inSource, inKey.exp, inKey.mod);
}
 
//
uint64_t Decrypt(const uint64_t inSource, const Key & inKey)
{
	return modpow(inSource, inKey.exp, inKey.mod);
}

The example above uses very low prime numbers. It is recommended to use n be least 2048 bits long.

It should output the following

Message    Encrypt    Decrypt
      0          0          0
      1          1          1
      2         32          2
      3        243          3
      4         55          4
      5        218          5
      6         24          6
      7         11          7
      8        145          8
      9        263          9
     10        193         10
     11        197         11
     12        122         12
     13        166         13
     14         29         14
     15          2         15
     16        118         16
     17        272         17
     18         18         18
     19        304         19
     20         39         20
     21         89         21
     22        167         22
     23        245         23
     24         28         24
     25         43         25
     26        144         26
     27        278         27
     28        282         28
     29          3         29
     30         64         30
     31         46         31
     32        223         32
     33         67         33
     34        306         34
     35        137         35
     36        253         36
     37         56         37
     38         38         38
     39        286         39
     40        279         40
     41        300         41
     42        264         42
     43        161         43
     44        176         44
     45        163         45
     46         88         46
     47        149         47
     48        250         48
     49        121         49
     50         84         50
     51        204         51
     52         86         52
     53        287         53
     54        175         54
     55        310         55
     56        303         56
     57        228         57
     58         96         58
     59        298         59
     60        110         60
     61         74         61
     62        180         62
     63        309         63
     64         30         64
     65         12         65
     66        206         66
     67        288         67
     68        102         68
     69        103         69
     70        185         70
     71        124         71
     72         21         72
     73         99         73
     74        177         74
     75        113         75
     76        247         76
     77        229         77
     78        108         78
     79        129         79
     80        207         80
     81         47         81
     82        233         82
     83         87         83
     84         50         84
     85        187         85
     86        307         86
     87         83         87
     88        141         88
     89        242         89
     90         48         90
     91        211         91
     92        232         92
     93        196         93
     94        246         94
     95         57         95
     96        248         96
     97        241         97
     98        319         98
     99        131         99
    100        104        100
    101        271        101
    102         68        102
    103         69        103
    104        168        104
    105         22        105
    106        140        106
    107         65        107
    108        109        108
    109        181        109
    110        230        110
    111         42        111
    112          6        112
    113        265        113
    114        190        114
    115        115        115
    116        165        116
    117         53        117
    118        169        118
    119         85        119
    120        290        120
    121         49        121
    122        107        122
    123        225        123
    124        269        124
    125          7        125
    126        198        126
    127        128        127
    128        314        128
    129         40        129
    130         61        130
    131        139        131
    132        132        132
    133        114        133
    134        172        134
    135        203        135
    136         34        136
    137        188        137
    138         66        138
    139          5        139
    140        106        140
    141         31        141
    142         92        142
    143         79        143
    144         26        144
    145          8        145
    146        261        146
    147         10        147
    148        173        148
    149        251        149
    150         63        150
    151        189        151
    152        152        152
    153        153        153
    154        222        154
    155         15        155
    156        226        156
    157        123        157
    158        252        158
    159        296        159
    160        164        160
    161        111        161
    162        212        162
    163        159        163
    164         27        164
    165         71        165
    166        200        166
    167         97        167
    168        308        168
    169        101        169
    170        170        170
    171        171        171
    172        134        172
    173        260        173
    174         72        174
    175        150        175
    176        313        176
    177         62        177
    178        315        178
    179        297        179
    180        244        180
    181        231        181
    182        292        182
    183        217        183
    184        318        184
    185        257        185
    186        135        186
    187        289        187
    188        120        188
    189        151        189
    190        209        190
    191        191        191
    192        184        192
    193        262        193
    194        283        194
    195          9        195
    196        195        196
    197        125        197
    198        316        198
    199         54        199
    200         98        200
    201        216        201
    202        274        202
    203         33        203
    204        238        204
    205        154        205
    206        270        206
    207        158        207
    208        208        208
    209        133        209
    210         58        210
    211        317        211
    212        281        212
    213         93        213
    214        142        214
    215        214        215
    216        258        216
    217        183        217
    218        301        218
    219        155        219
    220        254        220
    221        255        221
    222         52        222
    223        219        223
    224        192        224
    225          4        225
    226         82        226
    227         75        227
    228        266        228
    229         77        229
    230        127        230
    231         91        231
    232        112        232
    233        275        233
    234         81        234
    235        182        235
    236        240        236
    237         16        237
    238        136        238
    239        273        239
    240        236        240
    241         90        241
    242        276        242
    243        116        243
    244        194        244
    245        215        245
    246         94        246
    247         76        247
    248        210        248
    249        146        249
    250        224        250
    251        302        251
    252        199        252
    253        138        253
    254        220        254
    255        221        255
 
Encoded Message: 
	84 > 50
	104 > 168
	105 > 22
	115 > 115
	32 > 223
	105 > 22
	115 > 115
	32 > 223
	97 > 241
	32 > 223
	116 > 165
	101 > 271
	115 > 115
	116 > 165
	0 > 0
This is a test
 
Decoded Message: 
	50 > 84
	168 > 104
	22 > 105
	115 > 115
	223 > 32
	22 > 105
	115 > 115
	223 > 32
	241 > 97
	223 > 32
	165 > 116
	271 > 101
	115 > 115
	165 > 116
	0 > 0
This is a test

IPv4 UDP Broadcast

Whilst doing some networking code recently, I came by something I didn’t know about, UDP Broadcasting.

With TCP, both clients have knowledge of each other once a connection is formed. Because of this, you cannot just send a message to anyone listening, there has to be someone there.

With UDP, the host can transmit packets whether or not clients are connected and listening or not, and it will only know if they are there if it is listening and they are transmitting. But the client has to know about the host to begin listening.

Just like there is 127.0.0.1 (known as the loopback address) to send packets back to itself, 255.255.255.255 (known as the broadcast address) will allow packets to be sent to all addresses listening to a port.

Here is some basic code for sending and receive a broadcast.

//
const in_port_t broadcastPort = 12345;
 
//
void broadcast_send()
{
	// ooo datagrams
	int sockfd = socket(PF_INET, SOCK_DGRAM, 0);
 
	//
	struct sockaddr_in broadcastAddress;
	memset(&broadcastAddress, 0, sizeof(broadcastAddress));
	{
		broadcastAddress.sin_family = AF_INET;
		broadcastAddress.sin_addr.s_addr = htonl(INADDR_BROADCAST);
		broadcastAddress.sin_port = htons(broadcastPort);
	}
 
	// allow broadcasts
	const int enableBroadcast = 1;
	setsockopt(sockfd, SOL_SOCKET,SO_BROADCAST, &enableBroadcast, sizeof(enableBroadcast));
 
	// send to broadcast address
	const char message[] = "Test";
	sendto(sockfd, message, sizeof(message), 0, (struct sockaddr *)&broadcastAddress, sizeof(broadcastAddress));
}
 
//
void broadcast_receive()
{
	const size_t kMaxMessageLength = 200;
	char message[kMaxMessageLength];
 
	// ooo datagrams
	int sockfd = socket(PF_INET, SOCK_DGRAM, 0);
 
	//
	struct sockaddr_in recv_addr;
	memset(&recv_addr, 0, sizeof(recv_addr));
	{
		recv_addr.sin_family      = AF_INET;
		recv_addr.sin_addr.s_addr = htonl(INADDR_ANY);
		recv_addr.sin_port        = htons(broadcastPort);
	}
 
	//
	bind(sockfd, (struct sockaddr *)&recv_addr, sizeof(recv_addr));
 
	// allow broadcasts
	const int enableBroadcast = 1;
	setsockopt(sockfd, SOL_SOCKET, SO_BROADCAST, &enableBroadcast, sizeof(enableBroadcast));
 
	// receive
	struct sockaddr_in senderAddress;
	socklen_t senderLength = sizeof(senderAddress);
 
	ssize_t length = recvfrom(sockfd,
				  message, kMaxMessageLength,
				  0,
				  (struct sockaddr *)&senderAddress, &senderLength);
 
	if(length >= 0)
	{
		printf("Message received: %s\n", message);
	}
}

When a packet is sent using the broadcast address, all attached network hosts that are listening on the port will receive the packet.

This can be used for LAN multiplayer, as a way of advertising a game being available to join, or to seek games that are looking for players.

New Theme

I’ve changed the site theme after a long. This one works with mobile too, though is based on resolution rather than being a mobile device.

I looks much tidier and I like the font much more.

Objective-C Reflection

For glDebug I generate a lot of code so save having to write and update it, both for the call intercept library, and the application. More recently in the application, I’ve added an event list similar to the one in PIX where it shows the parameters.
Screen Shot 2014-04-28 at 04.37.46

So to generate this, I generate an overload of my base command class for every method, and changing the description function to return based on the parameter type and function name.

Then to create the class, I just get the class by the function name prefixed with “GLDebug_”.

Class createClass = NSClassFromString([NSString stringWithFormat:@"GLDebug_%@", commandName]);
 
//
if(createClass == nil)
{
	createClass = [CommandData class];
}
 
//				
CommandData * commandData = [[createClass alloc] initWithPacket:packet];

Now in my outline view I can just use the description string. One limitation however is I want to replace GLenum with the correct enum string. However it appears there are some enums sharing the same name. I may need to generate a spreadsheet and fill out the enums manually.

Coder in Progress