PHP Code: Simple Encryption Algorithm

This is a very simple Encryption Algorithm that uses the Caesar Shift Decoder (also called the Caesar Cipher).

The encryption is not limited to 25 characters though but is limited to the ASCII table moving each character a random amount of numbers forward.

Here is how it works:

1) Generate a Random Number


PHP Code:
// Create a Random Generator
srand((double)microtime()*1000000); // Seed the Random Generator
$strCharNumber = rand(102,106); // Pics a number between 102 and 106

This code will be the variable for how many characters the encryption scheme will be moved forward. As you can see, it is between 102 and 106.

2) Add this character to our final string output


PHP Code:
$strcode = chr($strCharNumber); // Add char to ending String

This allows us to grab that character and decrypt the entire string. This makes the code very unsecure as anyone that knows that is the decoding character can decode this message.

3) Encode the rest of the string. Lets say you received a [b]g[/g] which is 103 ascii value. For each character you would get the ascii value and move it up 103 values in the ascii table.


PHP Code:
// For Loop to convert each char into ascii then increase number
for ($i = 0; $i < strlen($name); $i++) {
$strChar = ord($name[$i]) + $strCharNumber;

4) In my code I also converted to hex but you can leave this step out if you like.


PHP Code:
$strChar = bin2hex(chr($strChar));

5) Add the string to the final string and close the for loop.


PHP Code:
$strcode = $strcode & $strChar;
}
?>

I've also attached a working copy of the PHP script. Let me know if you have any questions!
Attached FilesTo view attachments your post count must be 1 or greater. Your post count is 0 momentarily.

TEA Encryption Algorithm Source

The source is available under the MIT license. Download code and the testing program (CodeTea.zip: date 2007.02.07, size 11 949 bytes, md5 6c616ebb62ee7f87fd1460f8ad5510b6)

The unit uTeaSet.pas implements TEA, XTEA, Block TEA and XXTEA algorithms. This is a direct translation from the original C code by David Wheeler & Roger Needham, Cambridge University Computer Lab:

TEA: http://www.cl.cam.ac.uk/ftp/papers/djw-rmn/djw-rmn-tea.html (1994)
XTEA, Block TEA: http://www.cl.cam.ac.uk/ftp/users/djw3/xtea.ps (1997)
XXTEA: http://www.cl.cam.ac.uk/ftp/users/djw3/xxtea.ps (1998)
The unit also contains some useful routines.

unit uTeaSet;
{Pascal/Delphi implementation of TEA - Tiny Encryption Algorithm
Algorithms: TEA, XTEA, BlockTEA, XXTEA
author: Nikolai Shokhirev
created: April 04, 2004
modified: May 05, 2004
last modified: February 17, 2006 - corrected XTeaEncrypt/XTeaDecrypt
Thanks to Pedro Gimeno Fortea }

interface

const
Delta: longword = $9e3779b9;

type

TLong2 = array[0.. 1] of Longword; // 64-bit
TTeaKey = array[0..3] of longword; // 128-bit
TByte16 = array[0..15] of byte; // 128-bit
TByte4 = array[0..3] of byte; // 32-bit
TTeaData = array of longword; // n*32-bit
TByteArrData = array of byte; // n*8-bit

// Algorithm: David Wheeler & Roger Needham, Cambridge University Computer Lab
// TEA: http://www.cl.cam.ac.uk/ftp/papers/djw-rmn/djw-rmn-tea.html (1994)
procedure TeaEncrypt(var data: TLong2; const key: TTeaKey);
procedure TeaDecrypt(var data: TLong2; const key: TTeaKey);

// Algorithm: David Wheeler & Roger Needham, Cambridge University Computer Lab
// XTEA: http://www.cl.cam.ac.uk/ftp/users/djw3/xtea.ps (1997)
procedure XTeaEncrypt(var data: TLong2; const key: TTeaKey; N: Longword = 32);
procedure XTeaDecrypt(var data: TLong2; const key: TTeaKey; N: Longword = 32);

// Algorithm: David Wheeler & Roger Needham, Cambridge University Computer Lab
// Block TEA: http://www.cl.cam.ac.uk/ftp/users/djw3/xtea.ps (1997)
procedure BlockTeaEncrypt(data: TTeaData; const key: TTeaKey);
procedure BlockTeaDecrypt(data: TTeaData; const key: TTeaKey);

// Algorithm: David Wheeler & Roger Needham, Cambridge University Computer Lab
// XXTEA: http://www.cl.cam.ac.uk/ftp/users/djw3/xxtea.ps (1998)
procedure XXTeaEncrypt(data: TTeaData; const key: TTeaKey);
procedure XXTeaDecrypt(data: TTeaData; const key: TTeaKey);

// comparison of TTeaKey type variables
function SameKey(const key1, key2: TTeaKey): boolean;

// Conversion routines
procedure StrToKey(const s: string; var key: TTeaKey);
function KeyToStr(const key: TTeaKey): string;

// Conversion routines
procedure StrToData(const s: string; var data: TTeaData);
procedure DataToStr(var s: string; const data: TTeaData);

// reads a file of longword
procedure ReadData(const FileName: string; var data: TTeaData);
// writes a file of longword
procedure WriteData(const FileName: string; var data: TTeaData);

implementation

uses
math, SysUtils;

procedure TeaEncrypt(var data: TLong2; const key: TTeaKey);
var
y,z,sum: Longword;
a:byte;
begin
y:=data[0];
z:=data[1];
sum:=0;
for a:=0 to 31 do
begin
{ c code:
sum += delta;
y += (z << 4)+key[0] ^ z+sum ^ (z >> 5)+key[1];
z += (y << 4)+key[2] ^ y+sum ^ (y >> 5)+key[3];
}
inc(sum,Delta);
inc(y,((z shl 4)+key[0]) xor (z+sum) xor ((z shr 5)+key[1]));
inc(z,((y shl 4)+key[2]) xor (y+sum) xor ((y shr 5)+key[3]));
end;
data[0]:=y;
data[1]:=z
end;

procedure TeaDecrypt(var data: TLong2; const key: TTeaKey);
var
y,z,sum: Longword;
a:byte;
begin
y:=data[0];
z:=data[1];
sum:=delta shl 5;
for a:=0 to 31 do
begin
{ c code:
z -= (y << 4)+key[2] ^ y+sum ^ (y >> 5)+key[3];
y -= (z << 4)+key[0] ^ z+sum ^ (z >> 5)+key[1];
sum -= delta;
}
dec(z,((y shl 4)+key[2]) xor (y+sum) xor ((y shr 5)+key[3]));
dec(y,((z shl 4)+key[0]) xor (z+sum) xor ((z shr 5)+key[1]));
dec(sum,Delta);
end;
data[0]:=y;
data[1]:=z
end;

procedure XTeaEncrypt(var data: TLong2; const key: TTeaKey; N: Longword = 32);
var
y,z,sum,limit: Longword;
begin
y:=data[0];
z:=data[1];
sum:=0;
limit := Delta*N;
while sum <> limit do
begin
{ c code:
y += (z << 4 ^ z >> 5) + z ^ sum + key[sum&3];
sum += delta;
z += (y << 4 ^ y >> 5) + y ^ sum + key[sum>>11 & 3];
}
// inc(y,((z shl 4) xor (z shr 5)) xor (sum+key[sum and 3]));
inc(y,(((z shl 4) xor (z shr 5)) + z) xor (sum+key[sum and 3]));
inc(sum,Delta);
// inc(z,((y shl 4) xor (y shr 5)) xor (sum+key[(sum shr 11) and 3]));
inc(z,(((y shl 4) xor (y shr 5)) + y) xor (sum+key[(sum shr 11) and 3]));
end;
data[0]:=y;
data[1]:=z
end;

procedure XTeaDecrypt(var data: TLong2; const key: TTeaKey; N: Longword = 32);
var
y,z,sum: Longword;
begin
y:=data[0];
z:=data[1];
sum:=Delta*N;
while sum <> 0 do
begin
{ c code:
z -= (y << 4 ^ y >> 5) + y ^ sum + key[sum>>11 & 3];
sum -= delta;
y -= (z << 4 ^ z >> 5) + z ^ sum + key[sum&3];
}
// dec(z,((y shl 4) xor (y shr 5)) xor (sum+key[(sum shr 11) and 3]));
dec(z,(((y shl 4) xor (y shr 5)) + y) xor (sum+key[(sum shr 11) and 3]));
dec(sum,Delta);
// dec(y,((z shl 4) xor (z shr 5)) xor (sum+key[sum and 3]));
dec(y,(((z shl 4) xor (z shr 5)) + z) xor (sum+key[sum and 3]));
end;
data[0]:=y;
data[1]:=z
end;

procedure BlockTeaEncrypt(data: TTeaData; const key: TTeaKey);
var
z, y, sum, e, p: longword;
q, n: integer;

function mx: longword;
begin
result := (((z shl 4) xor (z shr 5)) + z) xor (key[(p and 3) xor e] + sum);
end;

begin
n := Length(data);
q := 6 + 52 div n;
z := data[n-1];
sum := 0;
repeat
inc(sum,Delta);
e := (sum shr 2) and 3;
for p := 0 to n-1 do
begin
y := data[p];
inc(y,mx);
data[p] := y;
z := y;
end;
dec(q);
until q = 0;
end;

procedure BlockTeaDecrypt(data: TTeaData; const key: TTeaKey);
var
z, y, sum, e, p, q: longword;
n: integer;

function mx: longword;
begin
result := (((z shl 4) xor (z shr 5)) + z) xor (key[(p and 3) xor e] + sum);
end;

begin
n := Length(data);
q := 6 + 52 div n;
sum := q*Delta;
while sum <> 0 do
begin
e := (sum shr 2) and 3;
for p := n-1 downto 1 do
begin
z := data[p-1];
y := data[p];
dec(y,mx);
data[p] := y;
end;
z := data[n-1];
y := data[0];
dec(y,mx);
data[0] := y;
dec(sum,Delta);
end;
end;

procedure XXTeaEncrypt(data: TTeaData; const key: TTeaKey);
var
z, y, x, sum, e, p: longword;
q, n: integer;

function mx: longword;
begin
result := (((z shr 5) xor (y shl 2)) + ((y shr 3) xor (z shl 4))) xor ((sum xor y) + (key[(p and 3) xor e] xor z) );
end;

begin
n := Length(data);
q := 6 + 52 div n;
z := data[n-1];
y := data[0];
sum := 0;
repeat
inc(sum,Delta);
e := (sum shr 2) and 3;
for p := 0 to n-2 do
begin
y := data[p+1];
x := data[p];
inc(x,mx);
data[p] := x;
z := x;
end;
y := data[0];
x := data[n-1];
inc(x,mx);
data[n-1] := x;
z := x;
dec(q);
until q = 0;
end;

procedure XXTeaDecrypt(data: TTeaData; const key: TTeaKey);
var
z, y, x, sum, e, p, q: longword;
n: integer;

function mx: longword;
begin
result := (((z shr 5) xor (y shl 2)) + ((y shr 3) xor (z shl 4))) xor ((sum xor y) + (key[(p and 3) xor e] xor z) );
end;

begin
n := Length(data);
q := 6 + 52 div n;
z := data[n-1];
y := data[0];
sum := q*Delta;
while sum <> 0 do
begin
e := (sum shr 2) and 3;
for p := n-1 downto 1 do
begin
z := data[p-1];
x := data[p];
dec(x,mx);
data[p] := x;
y := x;
end;
z := data[n-1];
x := data[0];
dec(x,mx);
data[0] := x;
y := x;
dec(sum,Delta);
end;
end;

function SameKey(const key1, key2: TTeaKey): boolean;
var
i: integer;
begin
result := false;
for i := 0 to 3 do
if key1[i] <> key2[i] then
exit;
result := true;
end;

procedure StrToKey(const s: string; var key: TTeaKey);
var
sa, sb: AnsiString;
i, n: integer;
begin
sa := AnsiString(s);
sb := StringOfChar(' ',16);
n := min(Length(sa),16);
for i := 1 to n do
sb[i] := sa[i];
for i := 1 to 16 do
TByte16(key)[i-1] := ord(sb[i]);
sa := '';
sb := '';
end;

function KeyToStr(const key: TTeaKey): string;
var
s: AnsiString;
i: integer;
begin
SetLength(s,16);
for i := 1 to 16 do
begin
s[i] := Chr(TByte16(key)[i-1]);
end;
result := s;
end;

procedure StrToData(const s: string; var data: TTeaData);
var
sa: AnsiString;
i, n, m: integer;
begin
sa := AnsiString(s);
n := Length(sa) div 4;
m := Length(sa) mod 4;
if m <> 0 then
begin
inc(n);
sa := sa + StringOfChar(' ',m);
end;
if n < 2 then // n = 1
begin
n := 2;
sa := sa + StringOfChar(' ',4);
end;

SetLength(data,n);
for i := 0 to n-1 do
for m := 0 to 3 do
TByte4(data[i])[m] := ord(sa[i*4+m+1]);
sa := '';
end;

procedure DataToStr(var s: string; const data: TTeaData);
var
sa: AnsiString;
i, n, m: integer;
b: byte;
begin
n := Length(data);
SetLength(sa,n*4);
for i := 0 to n-1 do
for m := 0 to 3 do
begin
b := TByte4(data[i])[m];
sa[i*4+m+1] := Chr(b);
end;
s := Trim(sa);
sa := '';
end;

procedure ReadData(const FileName: string; var data: TTeaData);
var
i, n: integer;
ww: longword;
wwf: file of longword;
begin
try
AssignFile(wwf,FileName);
Reset(wwf);
n := FileSize(wwf);
SetLength(data,n);
for i := 0 to n-1 do
begin
read(wwf,ww);
data[i] := ww;
end;
finally
CloseFile(wwf);
end;
end;

procedure WriteData(const FileName: string; var data: TTeaData);
var
i, n: integer;
ww: longword;
wwf: file of longword;
begin
try
AssignFile(wwf,FileName);
Rewrite(wwf);
n := Length(data);
for i := 0 to n-1 do
begin
ww := data[i];
write(wwf,ww);
end;
finally
CloseFile(wwf);
end;
end;

end.

Cryptographic Algorithms

3-Way
3-Way is a simple and fast cipher designed by Joan Daemen. 3-Way features a 96-bit key length and a 96-bit block length. 3-Way is an iterated block cipher that repeats some relatively simple operations a specified number of rounds. David Wagner, John Kelsey, and Bruce Schneier of Counterpane Systems have discovered a related key attack on 3-Way that requires one related key query and about 222 chosen plaintexts, described in this paper. 3-Way is unpatented.

Blowfish
Blowfish is a block cipher designed by Bruce Schneier, author of Applied Cryptography. Blowfish combines a Feistel network, key-dependent S-Boxes, and a non-invertible F function to create what is perhaps one of the most secure algorithms available. Schneier's paper is available here. Blowfish is also described in the Concepts of Cryptography page. The only known attacks against Blowfish are based on its weak key classes.

Blowfish is implemented in Kremlin.

CAST
CAST, designed by Carlisle Adams and Stafford Taveres, is shaping up to be a solid algorithm. Its design is very similar to Blowfish's, with key-dependent S-Boxes, a non-invertible f function, and a Feistel network-like structure (called a substitution-permutation network). David Wagner, John Kelsey, and Bruce Schneier have discovered a related-key attack on the 64-bit version of CAST that requires approximately 217 chosen plaintexts, one related query, and 248 offline computations (described in this paper). The attack is infeasible at best. CAST is patented by Entrust Technologies, which has generously released it for free use. The CAST cipher design process is described in this paper and the 128-bit version is described in this addendum. Carlisle Adams has submitted a version of CAST (CAST-256) as an AES candidate.

CAST-128 is implemented in Kremlin.

CMEA
CMEA is the encryption algorithm developed by the Telecommunications Industry Association to encrypt digital cellular phone data. It uses a 64-bit key and features a variable block length. CMEA is used to encrypt the control channel of cellular phones. It is distinct from ORYX, an also insecure stream cipher that is used to encrypt data transmitted over digital cellular phones. It has been broken by David Wagner, John Kelsey, and Bruce Schneier of Counterpane Systems. Their paper, which also provides an excellent description of the CMEA algorithm, is available here.

DES
Designed at IBM during the 1970s and officially adopted as the NIST standard encryption algorithm for unclassified data in 1976, DES has become the bastion of the cryptography market. However, DES has since become outdated, its long reign as official NIST algorithm ending in 1997. Though DES accepts a 64-bit key, the key setup routines effectively discard 8 bits, giving DES a 56-bit effective keylength. DES remains widely in use. During the design of DES, the NSA provided secret S-Boxes. After differential cryptanalysis had been discovered outside the closed fortress of the NSA, it was revealed that the DES S-boxes were designed to be resistant against differential cryptanalysis. DES is becoming weaker and weaker over time; modern computing power is fast approaching the computational horsepower needed to easily crack DES.

DES was designed to be implemented only in hardware, and is therefore extremely slow in software. A recent successful effort to crack DES took several thousand computers several months. The EFF has sponsored the development of a crypto chip named "Deep Crack" that can process 88 billion DES keys per second and has successfully cracked 56 bit DES in less than 3 days.

DES is implemented in Kremlin (accessible through Kremlin SDK API).

Triple-DES
A variant of DES, Triple-DES (also 3DES) is based on using DES three times. This means that the input data is encrypted three times. The Triple-DES is considered much stronger than DES, however, it is rather slow compared to some new block ciphers.


DEAL
DEAL is an interesting AES submission and, like all AES submissions, it uses a 128 bit block and accepts 128 bit, 192 bit, and 256 bit keylengths. It uses DES as its inner round function and its authors suggest at least 6, preferably 8 rounds (there are some attacks against DEAL). There is a paper available here that describes some attacks, all of which can be cured by using at least 8 rounds.

FEAL
Developed by the Nippon Telephone & Telegraph as an improvement to DES, the Fast Data Encipherment Algorithm (FEAL) is very insecure. FEAL-4, FEAL-8, and FEAL-N are all susceptible to a variety of cryptanalytic attacks, some requiring as little as 12 chosen plaintexts. FEAL is patented.

GOST
GOST is a cryptographic algorithm from Russia that appears to be the Russian analog to DES both politically and technologically. Its designers took no chances, iterating the GOST algorithm for 32 rounds and using a 256 bit key. Although GOST's conservative design inspires confidence, John Kelsey has discovered a key-relation attack on GOST, described in a post to sci.crypt on 10 February 1996. There are also weak keys in GOST, but there are too few to be a problem when GOST is used with its standard set of S-boxes. You can read the official GOST algorithm description (translated from Russian) here. There is also a description of the GOST algorithm here.

IDEA
IDEA, developed in Zurich, Switzerland by Xuejia Lai and James Massey, is generally regarded to be one of the best and most secure block algorithm available to the public today. It utilizes a 128-bit key and is designed to be resistant to differential cryptanalysis. Some attacks have been made against reduced round IDEA. Unfortunately, IDEA is patented; licensing information can be obtained from Ascom.

LOKI
LOKI was designed as a possible replacement for DES. It operates on a 64-bit block and a 64-bit key. The first version of LOKI to be released was broken by differential cryptanalysis and was shown to have an 8-bit complementation property (this means that the number of keys that need to be searched in a brute force attack is reduced by 256). LOKI was revised and re-released as LOKI91. LOKI91 is secure against differential cryptanalysis, but LOKI easily falls to a chosen-key attack. The designers of LOKI have proposed LOKI97 as an AES candidate, but linear and differential attacks on LOKI97 have already been proposed.

Lucifer
Lucifer was one of the first modern cryptographic algorithms. It was designed at IBM in the 1960s by Horst Feistel, of Feistel network fame. Lucifer is often considered to be a precursor to DES. There are several incarnations of Lucifer, each with the same name, which creates a good deal of confusion. No version is secure. A paper on the differential cryptanlysis of Lucifer was written by Ishai Ben-Aroya & Eli Biham.

MacGuffin
MacGuffin is a cipher developed by Matt Blaze and Bruce Schneier as an experiment in cipher design. It uses a Feistel network (see the cryptography overview for details), but does not split the input evenly, instead dividing the 64 bit block into one 16 bit part and another 48 bit part. This is called a generalized unbalanced Feistel network (GUFN). Details are available here. A differential attack on MacGuffin has been found that requires approximately 251.5 chosen plaintexts.

MARS
MARS is IBM's AES submission. There is a MARS web page with a link to the MARS paper. MARS uses 128 bit blocks and supports variable key sizes (from 128 to 1248 bits). MARS is unique in that it combines virtually every design technique known to cryptographers in one algorithm. It uses addition and subtractions, S-boxes, fixed and data dependent rotations, and multiplications.

MISTY
Misty is a cryptographic algorithm developed by Mitsubishi Electric after they broke DES in 1994. It is designed to withstand linear and differential cryptanalysis, but has not yet been cryptanalysed. As it has not undergone intensive peer review, the usual caution is recommended. It is being considered for inclusion into the SET 2.0 standard. Visit the MISTY web page or read the author's paper on MISTY.

MMB
MMB was designed as an alternative to IDEA that uses a 128-bit block instead of IDEA's 64-bit block. It was designed using the same principles as IDEA. Unfortunately, it is not as secure as IDEA and several attacks exist against it. Its author, Joan Daemen, abandoned it and designed 3-Way.

NewDES
Although NewDES was developed by Robert Scott to possibly replace DES, NewDES has fallen short of expectations. NewDES has been proven to be weaker than DES, requiring 24 related-key probes and 530 chosen plaintext/ciphertext queries, as described in this paper.

NewDES is implemented in Kremlin

RC2
RC2, like RC4, was formerly a trade secret, but code purporting to be RC2 was posted to sci.crypt. It is archived here. David Wagner, John Kelsey, and Bruce Schneier have discovered a related-key attack on RC2 that requires one related-key query and approximately 234 chosen plaintexts. RC2 is not patented by RSA Data Security, Inc; it is just protected as a trade secret.

RC5
RC5 is a group of algorithms designed by Ron Rivest of RSA Data Security that can take on a variable block size, key size, and number of rounds. The block size is generally dependent on the word size of the machine the particular version of RC5 was designed to run on; on 32-bit processors (with 32-bit words), RC5 generally has a 64-bit block size. David Wagner, John Kelsey, and Bruce Schneier have found weak keys in RC5, with the probability of selecting a weak key to be 2-10r, where r is the number of rounds. For sufficiently large r values (greater than 10), this is not a problem as long as you are not trying to build a hash function based on RC5. Kundsen has also found a differential attack on RC5. RC5 is described in this RSA document. RC5 is patented by RSA Security, Inc.

RC6
RC6 is Ronald Rivest's AES submission. Like all AES ciphers, RC6 works on 128 bit blocks. It can accept variable length keys. It is very similar to RC5, incorporating the results of various studies on RC5 to improve the algorithm. The studies of RC5 found that not all bits of data are used to determine the rotation amount (rotation is used extensively in RC5); RC6 uses multiplication to determine the rotation amount and uses all bits of input data to determine the rotation amount, strengthening the avalanche effect.

REDOC
There are two versions of the REDOC algorithm, REDOC II, and REDOC III. REDOC II is considered to be secure; an attack has been made against one round of REDOC II, but could not be extended to all 10 recommended rounds. REDOC II is interesting in that it uses data masks to select the values in the S-boxes. REDOC II uses a 160-bit key and works on an 80-bit block. REDOC III was an attempt to make the painfully slow REDOC II faster. REDOC III, like REDOC III, operates on an 80-bit block, but can accept keys up to 20480 bits. However, REDOC III falls to differential cryptanalysis, as described in this paper.

Rijndael
Rijndael is an AES winner by Joan Daemen and Vincent Rijmen. The cipher has a variable block and key length, and the authors have demonstrated how to extend the block length and key length by multiples of 32 bits. The design of Rijndael was influenced by the SQUARE algorithm. The authors provide a Rijndael specification and a more theoretical paper on their design principles. The authors have vowed to never patent Rijndael.

Safer
Safer was developed by Robert Massey at the request of Cylink Corporation. There are several different versions of Safer, with 40, 64, and 128-bit keys. A weakness in the key schedule was corrected, with an S being added to the original Safer K designation to create Safer SK. There are some attacks against reduced round variants of Safer. Safer is secure against differential and linear cryptanalysis. However, Bruce Schneier, author of Applied Cryptography, recommends against using Safer because, "Safer was designed for Cylink, and Cylink is tainted by the NSA."

Safer SK-128 is implemented in Kremlin.

Serpent
Serpent is an AES submission by Ross Anderson, Eli Biham, and Lars Knudsen. Its authors combined the design principles of DES with the recent development of bitslicing techniques to create a very secure and very fast algorithm. While bitslicing is generally used to encrypt multiple blocks in parallel, the designers of Serpent have embraced the technique of bitslicing and incorporated it into the design of the algorithm itself. Serpent uses 128 bit blocks and 256 bit keys. Like DES, Serpent includes an initial and final permutation of no cryptographic significance; these permutations are used to optimize the data before encryption. Serpent was released at the 5th International Workshop on Fast Software Encryption. This iteration of Serpent was called Serpent 0 and used the original DES S-boxes. After comments, the key schedule of Sperpent was changed slightly and the S-boxes were changed; this new iteration of Serpent is called Serpent 1. Serpent 1 resists both linear and differential attacks. The Serpent paper is available here.

SQUARE
SQUARE is an iterated block cipher that uses a 128-bit key length and a 128-bit block length. The round function of SQUARE is composed of four transformations: a linear transformation, a nonlinear transformation, a byte permutation, and a bitwise round-key addition. SQUARE was designed to be resistant to linear and differential cryptanalysis, and succeeds in this respect. The designers of SQUARE have developed an attack on SQUARE, but it cannot be extended past 6 rounds. A paper on SQUARE is available here and there are links to the paper and source code on the designers' web site.

Skipjack
In what surely signals the end of the Clipper chip project, the NSA has released Skipjack, its formerly secret encryption algorithm, to the public. Skipjack uses an 80 bit key. A fuzzy scan of the official NSA paper is available here at the NIST web site, but it has been transcribed by the folks over at jya.com. A reference implementation (in C) is available here, and an optimized version is available here. Eli Biham and Adi Shamir have published some initial cryptanalytic results (which are growing more and more interesting as time progresses).

Tiny Encryption Algorithm (TEA)
TEA is a cryptographic algorithm designed to minimize memory footprint, and maximize speed. However, the cryptographers from Counterpane Systems have discovered three related-key attacks on TEA, the best of which requires only 223 chosen plaintexts and one related key query. The problems arise from the overly simple key schedule. Each TEA key can be found to have three other equivalent keys, as described in a paper by David Wagner, John Kelsey, and Bruce Schneier. This precludes the possibility of using TEA as a hash function. Roger Needham and David Wheeler have proposed extensions to TEA that counter the above attacks.

Twofish
Twofish is Counterpane Systems' AES submission. Designed by the Counterpane Team (Bruce Schneier, John Kelsey, Doug Whiting, David Wagner, Chris Hall, and Niels Ferguson), Twofish has undergone extensive analysis by the Counterpane Team. There is a paper available from the Twofish web page and source is provided in optimized C and assembly.

Stream Ciphers


ORYX
ORYX is the algorithm used to encrypt data sent over digital cellular phones. It is a stream cipher based on three 32-bit Galois LFSRs. It is distinct from CMEA, which is a block cipher used to encrypt the cellular data control channel. The cryptographic tag-team from Counterpane Systems (David Wagner, John Kelsey, and Bruce Schneier) have developed an attack on ORYX that requires approximately 24 bytes of known plaintext and about 216 initial guesses.

RC4
The RC4 algorithm is a stream cipher from RSA Data Security, Inc. Though RC4 was originally a trade secret, the alleged source code was published anonymously in 1994. The published algorithm performs identically to RC4 implementations in official RSA products. RC4 is widely used in many applications and is generally regarded to be secure. There are no known attacks against RC4. RC4 is not patented by RSA Data Security, Inc; it is just protected as a trade secret.

The 40-bit exportable version of RC4 has been broken by brute force!

RC4 is implemented in Kremlin.

SEAL
SEAL, designed by Don Coppersmith of IBM Corp, is probably the fastest secure encryption algorithm available. The key setup process of SEAL requires several kilobytes of space and rather intensive computation involving SHA1, but only five operations per byte are required to generate the keystream. SEAL is particularly appropriate for disk encryption and similar applications where data must be read from the middle of a ciphertext stream. A paper is available here. SEAL is patented, and can be licensed from IBM.

Hash Algorithms


MD2
MD2 is generally considered to be a dead algorithm. It was designed to work on 8-bit processors and, in today's 32-bit world, is rarely used. It produces a 128-bit digest. MD2 is different in design from MD4 and MD5, in that it first pads the message so that its length in bits is divisible by 256. It then adds a 256-bit checksum. If this checksum is not added, the MD2 function has been found to have collisions. There are no known attacks on the full version of MD2. MD2 is described in RFC 1319.

MD4
Although MD4 is now considered insecure, its design is the basis for the design of most other cryptographic hashes and therefore merits description. First, the message to be operated on is padded so that its length in bits plus 448 is divisible by 512. Then, in what is called a Damgård/Merkle iterative structure, the message is processed with a compression function in 512-bit blocks to generate a digest value. In MD4 this digest is 128 bits long. Hans Dobbertin developed an attack on the full MD4 that will generate collisions in about a minute on most PCs. An overview of the design and a description of the security of MD2, MD4, and MD5, are described in this RSA document.

MD5
While MD4 was designed for speed, a more conservative approach was taken in the design of MD5. However, applying the same techniques he used to attack MD4, Hans Dobbertin has shown that collisions can be found for the MD5 compression function in about 10 hours on a PC. While these attacks have not been extended to the full MD5 algorithm, they still do not inspire confidence in the algorithm. RSA is quick to point out that these collision attacks do not compromise the integrity of MD5 when used with existing digital signatures. MD5, like MD4, produces a 128-bit digest. An RFC describing MD5 in detail is available here. The use of MD5, as well as MD4, is not recommended in new applications.

RIPEMD
RIPEMD and its successors were developed by the European RIPE project. Its authors found collisions for a version of RIPEMD restricted to two rounds. This attack can also be applied to MD4 and MD5. The original RIPEMD algorithm was then strengthened and renamed to RIPEMD-160. As implied by the name, RIPEMD-160 produces a 160-bit digest. A comprehensive description of RIPEMD-160 can be found here.

SHA1
SHA1 was developed by the NSA for NIST as part of the Secure Hash Standard (SHS). SHA1 is similar in design to MD4. The original published algorithm, known as SHA, was modified by NSA to protect against an unspecified attack; the updated algorithm is named SHA1. It produces a 160-bit digest -- large enough to protect against "birthday" attacks, where two different messages are selected to produce the same signature, for the next decade. The official FIPS description of SHA1 can be found here.

SHA1 is implemented in Kremlin.

Snefru

Snefru is a hash function designed by Ralph Merkle, the designer of the Khufu and Khafre encryption algorithms. 2-round Snefru has been broken by Eli Biham. Snefru 2.5, the latest edition of the hash algorithm, can generate either a 128-bit or a 256-bit digest.

Tiger
Tiger is a new hash algorithm by Ross Anderson and Eli Biham. It is designed to work with 64-bit processors such as the Digital Alpha and, unlike MD4, does not rely on rotations (the Alpha has no such rotate instruction). In order to provide drop-in compatibility with other hashes, Tiger can generate a 128-bit, a 160-bit or a 192-bit digest. The Tiger home page contains more information.

Blowfish Encryption Algorithm

Blowfish Source Code

• Reference source code from SSLeay 0.6.6
  
• C by Bruce Schneier
  
• C by Paul Kocher
  
• C++ (author unknown)
  
• C# and Java by Markus Hahn (very fast implementations)
  
• C++ by Jim Conger (note)
  
• C++ by Samuel Kabak
  
• Forth by Pierre Abbat
  
• Perl
  
  
• Visual Basic by David Ireland
  
  

Encryption Resources

Here are some books with good information on Encryption/Cryptography:

Cryptography: Theory and Practice - Douglas R. Stinson's Cryptography: Theory and Practice is a mathematically intensive examination of cryptography, including ciphers, the Data Encryption Standard (DES), public key cryptography, one-way hash functions, and digital signatures. Stinson's explication of "zero- sum proofs"--a process by which one person lets another person know that he or she has a password without actually revealing any information--is especially good.

SSH, The Secure Shell: The Definitive Guide - You can't go wrong with thisO'Rielly book - and this one is a mustall Unix users/admins as SSH quickly becomes a popular choice for securing remote transfers and connections.

Handbook of Applied Cryptography - A hefty handbook for both novices and experts, introducing practical aspects of conventional and public-key cryptography and offering information on the latest techniques and algorithms in the field. Mathematical treatments accompany practical discussions of areas including pseudorandom bits and sequences, stream and block ciphers, hash functions, and digital signatures.

Computer and Internet Ebooks - Helpful computer and Internet related ebooks.

The Internet has thousands of encryption/cryptography related resources. Here are a few that cover a broad range of topics:

Radius.net Software Archive - Your one stop shop for any and all encryption related software.

Phil Zimmermann's Homepage - The creator of PGP and a cryptography pioneer.

PGP Distribution site - MIT Distribution Center for PGP (Pretty Good Privacy).

Hushmail - Web based email with strong encryption.

AES - Information on AES (Advanced Encryption Standard) from NIST.

Cryptographic Toolkit - NIST's cryptography standard.

Windows 2000 Hight Encryption pack - Upgrade security on this popular operating system.

Encryption and Linux - The Linux Encryption-HOWTO Homepage.

Cipher - IEEE security and privacy newsletter.

C.R.I.S. - The Cryptography and Information Security Research Laboratory.

Encryption in the workplace - How electronic encryption works and how it will change your business.

Encryption and computer crime - Computer Crime and Intellectual Property Section (CCIPS).

Revised U.S. Encryption Export Control Regulations - As of January 2000.

Encryption Tools

There are many free and paid encryption tools available on the Internet. Some better than others, but nonetheless one can setup a secure messaging system (email encryption), secure transactions (SSL enabled web browsers) and secure connectivity (VPNs and SSH) on a very small budget. Some of the small business/individual solutions available include:


EMAIL
PGP - this is the defacto secure messaging standard on the Internet. Network Associates has dropped this product suite but fortunately the strong user base of PGP means it is likely to stay as the most popular email encryption tool.

Hushmail - here is another way of adding encryption to your email. But unlike software tools (say PGP) it is a service built into web based email. With free and paid service, one can get the flexibility of a web based email account combined with the security of 1,024-bit encryption, digital signatures and support for the OpenPGP standard.


FILE ENCRYPTION
Private File - Private File is a fast and easy way to protect yourself and your company by encrypting your files before sending them. With a simple drag-and-drop, or a menu point-and-click, your information is safe. And with the strongest encryption, you can be sure that no one but your desired recipient will be able to use your information.

F-Secure FileCrypto - developed by Datafellows Corp, this is a long standing file encryption application that supports strong encryption. Also comes for Pocket PC.

ShyFile - free and paid versions of a strong encryption application that lets you create self-executable, encrypted packages.


VPNs
Guardster - secure surfing and VPN type solution for individuals.

Secure Shuttle Transport - ideal solution for individuals or small businesses, providing complete VPN solution with a 20 user license.

PGP - certain versions of this applications allow point to point encrypted VPN sessions.

Windows NT/2000/XP & Linux - they allow 'secure' data transmssion between two nodes using the PPTP protocol.

Virtual Private Networks (VPNs)

Recent technological advances in broadband and dial data access offer a more cost-effective solution for supporting large numbers of remote users, as well as unprecedented network scalability and flexibility. These technology advances have created virtual private networks (VPN) using public links. They can be used to provide mobile workers with remote access to the corporate network - at the price of a local call. As with any use of public networks, one sacrifices privacy for cost and availability. Except a VPN is a network tunnel created for data transmission between two or more authenticated parties. A secure VPN encrypts data before passing it through the network tunnel. This creates an encrypted "pipe" between the user and the access device ensuring data integrity/authenticity, and user privacy. Apart from providing connectivity for remote users, VPNs can also be used to interconnect servers and complete networks, creating entities known as Extranets.





Virtual Private Networks can be implemented by using propreitory systems from Nortel Networks, Cisco, Datafellows, Intel, Nokia, Checkpoint, Lucent and others. Point to point VPNs can also be created using imbedded protocols in Operating Systems like Windows 2000/XP/Linux or even by applications like PGP.


IPSEC
The IP Security Protocol (IPSec) working group has defined a set of specifications for cryptographically-based authentication, integrity, and confidentiality services at the IP datagram layer. This protocol is intended to secure data communications on the Internet and is one of the fastest growing security standards worldwide. IPSec supports multiple algorithms and key management systems within its design architecture.

Most people associate VPNs with corporate or government use. But individual users can utilize the power of personal VPN services like Guardster. This service allow you to surf the Internet anonymously, use encrypted email, have private instant messaging, secure file transfers, etc. Secure Shuttle Transport is an ideal small business VPN solution, coming with a 20 user license while priced at well below $100.

Encrypted Email

One of the most common uses of encryption is in electronic messaging. Encryption can be used to secure email on public and private networks. Unlike e-mail on a private system, which goes directly to a mail server and resides there until it is retrieved, Internet e-mail bounces from server to server on its way to a recipient. This makes the transmission channel impossible to secure and provides numerous opportunities for interception. Here it makes sense to secure the message itself by using encryption. But private networks are not immune to the need for higher security and often employ encryption to guarantee the integrity of the message.

Sending plaintext email is like sending a postcard - what type of information do you disclose when mailing a postcard? When do you consider putting the letter in an envelope to resist tampering and to protect your privacy? Similarly, encrypting email is the first step to securing the contents of your message. One of the most popular methods of email encryption is the use of public key encryption.

The two most widely fielded methods of email encryption are PGP (Pretty Good Privacy) and Entrust. The former provides solutions for both individuals and corporations while Entrust focuses on the larger enterprise based secure messaging solutions. Also availabe to individual users/small businesses is encrypted email on a web based platform through Hushmail. This service allows you to send and receive email from their website, never having to buy any software or have the need for extra infrastructure.

Also available is S/MIME (Secure / Multipurpose Internet Mail Extensions) - a protocol that adds digital signatures and encryption to Internet MIME messages. The MIME format allows the body of the message to be text, graphics, audio/video, etc allowing one to encrypt multiple forms of newsgroup communications.

Encrypted mail enables the 'little guy' to decide how much privacy they want and when and where they want it. The Tools section has resources one could use for encrypted and anonymous email.

Planning on getting a new email address? Check this site out for email hosting options!

Cracking Encryption Algorithms

Need for secure encryption algorithms
Good cryptographic systems should always be designed so that they are as difficult to break as possible. Governments have always had concerns with strong encryption fearing that it could be used against their countries by criminals. Sophisticated technology is used by law enforcement agencies to decipher encrypted information that might contain incriminating evidence. In theory one can break any encryption algorithm by exhausting every key in a sequence. This brute force method requires vast amounts of computing power as length of the key increase. For example a 32-bit key takes 2^32 (4294967296) steps. A system with 40 bit keys (e.g. US-exportable version of RC4) takes 2^40 steps - this kind of computing power is available in most universities and even small companies.


Encryption key lengths & hacking feasibility
Type of Attacker Budget Tool Time & Cost/Key
40 bit Time & Cost/Key
56 bit
Regular User Minimal

$400 Scavenged computer time

FPGA 1 week

5 hours ($.08) Not feasible

38 years ($5,000)
Small Business $10,000 FPGA 1 12 min.($.08) 556 days ($5,000)
Corporate Department $300,000 FPGA

ASIC 2 24 sec. ($.08)

0.18 sec. ($.001) 19 days ($5,000)

3 hours ($38)
Large Corporation $10M ASIC 0.005 sec.($0.001) 6 min. ($38)
Intelligence Agency $300M ASIC 0.0002 sec.($0.001) 12 sec. ($38)


As key lengths increase, the number of combinations that must be tried for a brute force attack increase exponentially. For example a 128-bit key would have 2^128 (3.402823669209e+38) total possible combinations. For example, to theoretically crack the 128-bit IDEA key using brute force one would have to:


develop a CPU that can test 1 billion IDEA keys per second

build a parallel machine that consists of one million of these processors

mass produce them to an extent that everyone can own one hundred of these machines

network them all together and start working through the 128 bit key space
Assuming ideal performance and no downtime, one should be able to exhaustively search the key-space in over 20,000 years. A common concern amongst many is deciding what key length is secure. There is a metronome for technological progress called Moore's Law which states that; "the number of components that can be packed on a computer chip doubles every 18 months while the price stays the same" . Essentially, this means that computing power per dollar doubles every eighteen months. Using a derivative of this above law one can also say that, if a key length of x is considered safe today, in 18 months the key length would have to be x+1 to keep up to par with the computing power. Recent studies performed by independent scientists have shown that key lengths should be no less than 90-bits long to ensure complete security for the next 20 years.

1 FPGA (Field Programmable Gate Arrays) are programmable pieces of hardware specifically designed for encryption/decryption.

2 ASIC (Application Specific Integrated Circuits) are also specialized hardware that can test 200 million keys per second.

Public Key Encryption

1976 saw the introduction of a radical new idea into the field of cryptography. This idea centered around the premise of making the encryption and decryption keys different - where the knowledge of one key would not allow a person to find out the other. Public key encryption algorithms are based on the premise that each sender and recipient has a private key, known only to him/her and a public key, which can be known by anyone. Each encryption/decryption process requires at least one public key and one private key. A key is a randomly generated set of numbers/ characters that is used to encrypt/decrypt information.

A public key encryption scheme has six major parts:

Plaintext - this is the text message to which an algorithm is applied.

Encryption Algorithm - it performs mathematical operations to conduct substitutions and transformations to the plaintext.

Public and Private Keys - these are a pair of keys where one is used for encryption and the other for decryption.

Ciphertext - this is the encrypted or scrambled message produced by applying the algorithm to the plaintext message using key.

Decryption Algorithm - This algorithm generates the ciphertext and the matching key to produce the plaintext.


Selecting the Public and Private Keys
Select large prime numbers p and q and form n = pq.
Select an integer e > 1 such that GCD(e, (p - 1)(q - 1)) = 1.
Solve the congruence, ed º 1 (mod (p - 1), (q - 1))
for an integer d where 1 < d < (p - 1)(q - 1).
The public encryption key is (e,n).
The private encryption key is (d,n).
The Encryption Process
• The process of encryption begins by converting the text to a pre hash code. This code is generated using a mathematical formula.

• This pre hash code is encrypted by the software using the senders private key. The private key would be generated using the algorithm used by the software.

• The encrypted pre hash code and the message are encrypted again using the sender's private key.

• The next step is for the sender of the message to retrieve the public key of the person this information is intended for.

• The sender encrypts the secret key with the recipient's public key, so only the recipient can decrypt it with his/her private key, thus concluding the encryption process.


Lookup the user's public key (e , n ).
Make sure that the message M is an integer such that 0 £ M £ n.
Compute, M ^ e º C (mod n) where 0 £ C £ n.
Transmit the integer C.
The Decryption Process
• The recipient uses his/her private key to decrypt the secret key.

• The recipient uses their private key along with the secret key to decipher the encrypted pre hash code and the encrypted message.

• The recipient then retrieves the sender's public key. This public key is used to decrypt the pre hash code and to verify the sender's identity.

• The recipient generates a post hash code from the message. If the post hash code equals the pre hash code, then this verifies that the message has not been changed en-route.


Use your private key (d , n ).
Receive the integer C, where 0 £ C £ n.
Compute, C ^ d º R (mod n) where 0 £ R £ n.
R is the original message.
Featured article:
A Primer on Public Key Encryption
by Charles C. Mann.

How Encryption Works

The concept behind encryption is quite simple - make the data unlegible for everyone else except those specified. This is done using cyrptography - the study of sending 'messages' in a secret form so that only those authorized to receive the 'message' be able to read it.

The easy part of encryption is applying a mathematical function to the plaintext and converting it to an ecrypted cipher. The harder part is to ensure that the people who are supposed to decipher this message can do so with ease, yet only those authorised are able to decipher it. We of-course also have to establish the legitimacy of the mathematical function used to make sure that it is sufficiently complex and mathmatically sound to give us a high degree of safety.

The essential concept underlying all automated and computer security application is cyptography. The two ways of going about this process are conventional (or symmetric) encryption and public key (or asymmetic) encryption.

Featured articles:
A Primer on Public Key Encryption
by Charles C. Mann.

Introduction to Cryptography
by Peter Meyer.

Why Use Encryption?

As organizations and individuals have connected to the Internet in droves, many have begun eyeing its infrastructure as an inexpensive medium for wide-area and remote connections. The Internet is an international network consisting of individual computers and computer networks that are all interconnected by many paths. Unlike Local Area Networks where access is physically restricted to authorized users, the Internet is a public network and can be accessed by anyone.

Now more than ever, moving vast amounts of information quickly and safely across great distances is one of our most pressing needs. The basic idea of cryptography is to hide information from prying eyes. On the Internet this can be your credit card numbers, bank account information, health/social security information, or pseraonal correspondence with someone else.


History of Encryption
Encryption pre-dates the Internet by thousands of years. Looking back in history we find that Julius Caesar was an early user of cryptography. He sent messages to his troops in a simple but ingeneous method. A letter in the alphabet was replaced by one say 5 positions to the right. So, an "A" would be replaced by an "E", "B" by "F" and so on. Hence RETURN would become VJYZVS. But as it can be seen, this cipher can be easily broken by either figuring out a pattern, by brute force or by getting ones hands on a plaintext and ciphertext combination to deduce the pattern.


Users of Encryption
A few decades ago, only governments and diplomats used encryption to secure sensitive information. Today, secure encryption on the Internet is the key to confidence for people wanting to protect their privacy, or doing business online. E-Commerce, secure messaging, and virtual private networks are just some of the applications that rely on encryption to ensure the safety of data. In many companies that have proprietary or sensitive information, field personnel are required to encrypt their entire laptops fearing that in the wrong hands this information could cause millions of dollars in damage.

Encryption Algorithms

Different encryption algorithms use proprietory methods of generating these keys and are therefore useful for different applications. Here are some nitty gritty details about some of these encryption algorithms. Strong encyrption is often discerend by the key length used by the algorithm.


RSA
In 1977, shortly after the idea of a public key system was proposed, three mathematicians, Ron Rivest, Adi Shamir and Len Adleman gave a concrete example of how such a method could be implemented. To honour them, the method was referred to as the RSA Scheme. The system uses a private and a public key. To start two large prime numbers are selected and then multiplied together; n=p*q.

If we let f(n) = (p-1) (q-1), and e>1 such that GCD(e, f(n))=1. Here e will have a fairly large probability of being co-prime to f(n), if n is large enough and e will be part of the encryption key. If we solve the Linear Diophantine equation; ed congruent 1 (mod f(n)), for d. The pair of integers (e, n) are the public key and (d, n) form the private key. Encryption of M can be accomplished by the following expression; Me = qn + C where 0<= C < n. Decryption would be the inverse of the encryption and could be expressed as; Cd congruent R (mod n) where 0<= R < n. RSA is the most popular method for public key encryption and digital signatures today.


DES/3DES
The Data Encryption Standard (DES) was developed and endorsed by the U.S. government in 1977 as an official standard and forms the basis not only for the Automatic Teller Machines (ATM) PIN authentication but a variant is also utilized in UNIX password encryption. DES is a block cipher with 64-bit block size that uses 56-bit keys. Due to recent advances in computer technology, some experts no longer consider DES secure against all attacks; since then Triple-DES (3DES) has emerged as a stronger method. Using standard DES encryption, Triple-DES encrypts data three times and uses a different key for at least one of the three passes giving it a cumulative key size of 112-168 bits.


BLOWFISH
Blowfish is a symmetric block cipher just like DES or IDEA. It takes a variable-length key, from 32 to 448 bits, making it ideal for both domestic and exportable use. Bruce Schneier designed Blowfish in 1993 as a fast, free alternative to the then existing encryption algorithms. Since then Blowfish has been analyzed considerably, and is gaining acceptance as a strong encryption algorithm.


IDEA
International Data Encryption Algorithm (IDEA) is an algorithm that was developed by Dr. X. Lai and Prof. J. Massey in Switzerland in the early 1990s to replace the DES standard. It uses the same key for encryption and decryption, like DES operating on 8 bytes at a time. Unlike DES though it uses a 128 bit key. This key length makes it impossible to break by simply trying every key, and no other means of attack is known. It is a fast algorighm, and has also been implemented in hardware chipsets, making it even faster.


SEAL
Rogaway and Coppersmith designed the Software-optimized Encryption Algorithm (SEAL) in 1993. It is a Stream-Cipher, i.e., data to be encrypted is continuously encrypted. Stream Ciphers are much faster than block ciphers (Blowfish, IDEA, DES) but have a longer initialization phase during which a large set of tables is done using the Secure Hash Algorithm. SEAL uses a 160 bit key for encryption and is considered very safe.


RC4
RC4 is a cipher invented by Ron Rivest, co-inventor of the RSA Scheme. It is used in a number of commercial systems like Lotus Notes and Netscape. It is a cipher with a key size of up to 2048 bits (256 bytes), which on the brief examination given it over the past year or so seems to be a relatively fast and strong cypher. It creates a stream of random bytes and 'XORing' those bytes with the text. It is useful in situations in which a new key can be chosen for each message.

Interested in barcode scanners or barcode printers? Get them here today!

Base64 encode VBS function

Function Base64Encode(inData)
'rfc1521
'2001 Antonin Foller, Motobit Software, http://Motobit.cz
Const Base64 = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"
Dim cOut, sOut, I

'For each group of 3 bytes
For I = 1 To Len(inData) Step 3
Dim nGroup, pOut, sGroup

'Create one long from this 3 bytes.
nGroup = &H10000 * Asc(Mid(inData, I, 1)) + _
&H100 * MyASC(Mid(inData, I + 1, 1)) + MyASC(Mid(inData, I + 2, 1))

'Oct splits the long To 8 groups with 3 bits
nGroup = Oct(nGroup)

'Add leading zeros
nGroup = String(8 - Len(nGroup), "0") & nGroup

'Convert To base64
pOut = Mid(Base64, CLng("&o" & Mid(nGroup, 1, 2)) + 1, 1) + _
Mid(Base64, CLng("&o" & Mid(nGroup, 3, 2)) + 1, 1) + _
Mid(Base64, CLng("&o" & Mid(nGroup, 5, 2)) + 1, 1) + _
Mid(Base64, CLng("&o" & Mid(nGroup, 7, 2)) + 1, 1)

'Add the part To OutPut string
sOut = sOut + pOut

'Add a new line For Each 76 chars In dest (76*3/4 = 57)
'If (I + 2) Mod 57 = 0 Then sOut = sOut + vbCrLf
Next
Select Case Len(inData) Mod 3
Case 1: '8 bit final
sOut = Left(sOut, Len(sOut) - 2) + "=="
Case 2: '16 bit final
sOut = Left(sOut, Len(sOut) - 1) + "="
End Select
Base64Encode = sOut
End Function

Function MyASC(OneChar)
If OneChar = "" Then MyASC = 0 Else MyASC = Asc(OneChar)
End Function

Ambiguity Decorrelation algorithm

PROGRAM TEST
C
C FUNCTION: TEST Z_MATRIX SUBROUTINE FOR GPS SOLUTION - GPS TOOLBOX COLUMN
C
C SUBROUTINE CALLED:
C Z_MATRIX (Q,N,M,Z)
C
C VARIABLES:
C Q: Variance-covarinace matrix of the estimated real-value
C ambiguities before calling Z_MATRIX
C variance-covariance matrix of the transformed real-value
C ambiguities after calling Z_MATRIX.
C Z: Integer transformation matrix
C N: Defined row and column number of Q
C M: Number of ambiguities
C
IMPLICIT REAL*8 (A-H,O-Z)
IMPLICIT INTEGER*4 (I-N)
PARAMETER(N=16)
REAL*8 Q(N,N),Z(N,N)
C
OPEN(12,FILE='Q_X.TXT',STATUS='OLD')
OPEN(13,FILE='Z_Q.TXT',STATUS='UNKNOWN')
C
READ(12,*) M
DO I=1,M
READ(12,*) (Q(I,J),J=1,M)
ENDDO
C
C COMPUTE THE INTEGER TRANSFORMATION MATRIX
C
CALL Z_MATRIX (Q,N,M,Z)
C
WRITE(13,*) 'RESULTS:'
WRITE(13,*)
WRITE(13,*) 'Z='
DO I=1,M
WRITE(13,'(16F15.6)') (Z(I,J),J=1,M)
ENDDO
WRITE(13,*) 'Q='
DO I=1,M
WRITE(13,'(16F15.6)') (Q(I,J),J=1,M)
ENDDO
C
STOP
END
C
C
SUBROUTINE Z_MATRIX (Q,N,M,Z)
C
C FUNCTION: INTEGER TRANSFORMATION MATRIX DETERMINATION USING
C LDL' AND UDU' DECOMPOSITION METHOD (REF. HAN & RIZOS PAPER,
C TO BE APPEARED IN ION GPS-95 PROCEEDINGS).
C
C AUTHOR : SHAOWEI HAN
C DATE : JANUARY 10, 1995
C
C VARIABLES:
C Q: Variance-covarinace matrix of the estimated real-value
C ambiguities before calling Z_MATRIX;
C Variance-covariance matrix of the transformed real-value
C ambiguities after calling Z_MATRIX.
C Z: Integer transformation matrix
C N: Defined row and column number of Q from the parent program.
C It should be smaller than 30. Otherwise some subroutines
C (INT_TRIA, LOW_UDU, UP_UDU) need a minor modifications.
C M: Number of ambiguities, and smaller than N.
C N1: Choose the same constant value as N which was defined in the
C parent program.
C
C SUBROUTINES CALLED:
C INT_MATRIX: make every elements of the matrix round to nearest integer
C INV_TRIA: inverse of triangular matrix
C LOW_UDU: U-D decomposition Q=U*D*U', U is lower triangle matrix.
C MULTIPLE: multiplication of A and B => C.
C UP_UDU: U-D decomposition Q=U*D*U', U is upper triangle matrix.
C
IMPLICIT REAL*8 (A-H,O-Z)
IMPLICIT INTEGER*4 (I-N)
C
PARAMETER(N1=16)
REAL*8 Q(N,N),Z(N,N)
REAL*8 C(N1,N1),D(N1),U(N1,N1),Z1(N1,N1)
C
IZERO=0
IONE=1
NUMBER1=1
NUMBER2=1
C
DO I=1,M
Z(I,I)=1.D0
ENDDO
C
DO ITER=1,50
C
C 1. LOW_UDU DECOMPOSITION
C
60 CALL LOW_UDU(N,M,Q,U,D)
C
C 1.1 Round elements of U to integers (Z1)
C
CALL INT_MATRIX(N,M,Z1,U,NUMBER1)
C
C NUMBER1=0 means Z1 is identical matrix
C
IF ((NUMBER1.EQ.0).AND.(NUMBER2.EQ.0)) GOTO 100
IF (NUMBER1.GT.0) THEN
C
C 1.2 Inverse of Z1
C
CALL INV_TRIA(N,M,Z1,IZERO)
CALL MULTIPLE(Z1,Z,C,N,N,N,N,N,N,M,M,M,IZERO)
DO I=1,M
DO J=1,M
Z(I,J)=C(I,J)
ENDDO
ENDDO
ELSE
GOTO 70
ENDIF
C
C 1.3 Update transformation matrix Z and
C
CALL MULTIPLE(Z1,Q,C,N,N,N,N,N,N,M,M,M,IZERO)
CALL MULTIPLE(C,Z1,Q,N,N,N,N,N,N,M,M,M,IONE)
C
C 2. UP_UDU DECOMPOSITION
C
70 CALL UP_UDU(N,M,Q,U,D)
C
CALL INT_MATRIX(N,M,Z1,U,NUMBER2)
C
IF ((NUMBER1.EQ.0).AND.(NUMBER2.EQ.0)) GOTO 100
IF (NUMBER2.GT.0) THEN
CALL INV_TRIA(N,M,Z1,IONE)
CALL MULTIPLE(Z1,Z,C,N,N,N,N,N,N,M,M,M,IZERO)
DO I=1,M
DO J=1,M
Z(I,J)=C(I,J)
ENDDO
ENDDO
ELSE
GOTO 60
ENDIF
C
CALL MULTIPLE(Z1,Q,C,N,N,N,N,N,N,M,M,M,IZERO)
CALL MULTIPLE(C,Z1,Q,N,N,N,N,N,N,M,M,M,IONE)
C
ENDDO
C
100 CONTINUE
C
RETURN
END
C
C
SUBROUTINE INT_MATRIX(N,NR,Z,D,NUMBER)
C
C FUNCTION: MAKE EVERY ELEMENTS OF D ROUND TO NEAREST INTEGER
C
C AUTHOR : SHAOWEI HAN
C DATE : JANUARY 10, 1995
C
IMPLICIT REAL*8 (A-H)
IMPLICIT INTEGER*4 (I-N)
REAL*8 D(N,N),Z(N,N)
C
C DO I=1,NR
C DO J=1,NR
C Z(I,J)=0.
C ENDDO
C ENDDO
C
NUMBER=0
DO I=1,NR
DO J=1,NR
Z(I,J)=DNINT(D(I,J))
IF (Z(I,J).NE.0.) THEN
NUMBER=NUMBER+1
ENDIF
ENDDO
ENDDO
NUMBER=NUMBER-NR
RETURN
END
C
C
SUBROUTINE INV_TRIA(IP,N,P,IT)
C
C FUNCTION: INVERSE OF TRIANGULAR MATRIX
C
C AUTHOR : SHAOWEI HAN
C DATE : JANUARY 10, 1995
C
C VARIABLES:
C IT:=1 UPPER TRIANGULAR MATRIX
C =0 LOWER TRIANGULAR MATRIX
C IP: DEFINED DIMENSION OF Q
C N: THE REAL DIMENSION OF TRIANGLE MATRIX
C
C
IMPLICIT REAL*8(A-H,O-Z)
IMPLICIT INTEGER*4 (I-N)
REAL*8 P(IP,IP),Q(30,30)
C
DO I=1,30
DO J=1,30
Q(I,J)=0.D0
ENDDO
ENDDO
C
C INVERSE OF UPPER TRIANGLUAR MATRIX
C
IF (IT.EQ.1) THEN
DO K=1,N
Q(K,K)=1.D0/P(K,K)
DO I=K-1,1,-1
SUM=.0D0
DO J=I+1,K
SUM=SUM+P(I,J)*Q(J,K)
ENDDO
Q(I,K)=-SUM/P(I,I)
ENDDO
ENDDO
C
ELSE
C
C INVERSE OF LOW TRIANGLUAR MATRIX
C
DO K=1,N
Q(K,K)=1.D0/P(K,K)
DO I=K-1,1,-1
SUM=.0D0
DO J=I+1,K
SUM=SUM+P(J,I)*Q(K,J)
ENDDO
Q(K,I)=-SUM/P(I,I)
ENDDO
ENDDO
C
ENDIF
C
DO I=1,N
DO J=1,N
P(I,J)=Q(I,J)
ENDDO
ENDDO
RETURN
END
C
C
SUBROUTINE LOW_UDU(N,NR,Q,U,D)
C
C FUNCTION: U-D DECOMPOSITION Q=U*D*U' FROM P(1,1)=>P(N,N)
C U IS LOWER TRIANGLE MATRIX
C
C AUTHOR : SHAOWEI HAN
C DATE : 8TH JANUARY, 1995
C
C INPUT VARIABLES:
C N: DEFINED DIMENSION OF ARRAYS Q,U AND D
C NR: REAL DIMENSION OF ARRAYS Q,U AND D
C Q: Q WILL BE U-D DEPOSITION
C
C OUTPUT VARIABLES:
C U: LOW-TRIANGLE MATRIX
C D: DIAGONAL MATRIX
C
IMPLICIT REAL*8 (A-H,O-Z)
IMPLICIT INTEGER*4 (I-N)
REAL*8 Q(N,N),D(N),U(N,N),P(30,30)
C
DO J=1,N
D(J)=0.D0
DO K=1,N
U(J,K)=0.D0
ENDDO
ENDDO
C
DO J=1,N
DO K=1,N
P(J,K)=Q(J,K)
ENDDO
ENDDO
C
DO 5 J=1,NR-1
D(J)=P(J,J)
U(J,J)=1.
ALPHA=1./D(J)
DO 5 K=NR,J+1,-1
BETA=P(K,J)
U(K,J)=ALPHA*BETA
DO 5 I=K,NR
5 P(I,K)=P(I,K)-BETA*U(I,J)
U(NR,NR)=1.
D(NR)=P(NR,NR)
C
RETURN
END
C
C
SUBROUTINE MULTIPLE(A,B,C,IA,JA,IB,JB,IC,JC,M,N,L,IT)
C
C FUNCTION: MULTIPLICATION OF A AND B.
C IT=0: A(M,N)*B(N,L) => C(M,L)
C IT=1: A(M,N)*Transposed(B(L,N)) => C(M,L)
C AUTHOR : SHAOWEI HAN
C DATE : JANUARY 10, 1995
C
C VARIABLES:
C (IA, JA) IS THE DEFINED DIMENSION OF A
C (IB, JB) IS THE DEFINED DIMENSION OF B
C (IC, JC) IS THE DEFINED DIMENSION OF C
C
C A(M,N) IS THE MAIN SUBMATRIX FROM (1,1) OF A(IA,JA)
C B(N,L) IS THE MAIN SUBMATRIX FROM (1,1) OF B(IB,JB)
C C(M,L) IS THE MAIN SUBMATRIX FROM (1,1) OF C(IC,JC)
C
IMPLICIT REAL*8 (A-H)
IMPLICIT INTEGER*4 (I-N)
REAL*8 A(IA,JA),B(IB,JB),C(IC,JC)
IF (IT.EQ.0) THEN
DO I=1,M
DO J=1,L
H=0.D0
DO K=1,N
H=H+A(I,K)*B(K,J)
ENDDO
C(I,J)=H
ENDDO
ENDDO
C
ELSE
C
DO I=1,M
DO J=1,L
H=0.D0
DO K=1,N
H=H+A(I,K)*B(J,K)
ENDDO
C(I,J)=H
ENDDO
ENDDO
ENDIF
RETURN
END
C
C
SUBROUTINE UP_UDU(N,NR,Q,U,D)
C
C FUNCTION: U-D DECOMPOSITION P=U*D*U' FROM P(N,N)=>P(1,1)
C U IS UPPER TRIANGLE MATRIX
C AUTHOR : SHAOWEI HAN
C DATE : 8TH JANUARY, 1995
C
C INPUT VARIABLES:
C N: DEFINED DIMENSION OF ARRAYS Q,U AND D
C NR: REAL DIMENSION OF ARRAYS Q,U AND D
C Q: Q WILL BE U-D DEPOSITION
C
C OUTPUT VARIABLES:
C U: UP-TRIANGLE MATRIX
C D: DIAGONAL MATRIX
C
IMPLICIT REAL*8 (A-H,O-Z)
IMPLICIT INTEGER*4 (I-N)
REAL*8 Q(N,N),D(N),U(N,N),P(30,30)
C
DO J=1,N
D(J)=0.D0
DO K=1,N
U(J,K)=0.D0
ENDDO
ENDDO
C
DO J=1,N
DO K=1,N
P(J,K)=Q(J,K)
ENDDO
ENDDO
C
DO 5 J=NR,2,-1
D(J)=P(J,J)
U(J,J)=1.
ALPHA=1./D(J)
DO 5 K=1,J-1
BETA=P(K,J)
U(K,J)=ALPHA*BETA
DO 5 I=1,K
5 P(I,K)=P(I,K)-BETA*U(I,J)
U(1,1)=1.
D(1)=P(1,1)
RETURN
END

Date/Time conversion algorithms

/**********************************************************************
NOTE TO ALL USERS:

This file contains 6 main() programs and 12 C functions.
Before compiling with a C compiler, this file should be split into
6 files; each having one main program and two C functions. The six
files are separated by equal signs (========== name =============).


**********************************************************************/

/*============================= GPS_YD.C ===============================*/
#include
#include
#define JAN61980 44244
#define JAN11901 15385
#define SEC_PER_DAY 86400.0
void gps_to_ydhms(long gps_week, double sec_of_week,
long *year, long *yday, long *hour, long *minute, double *second);
void ydhms_to_gps(long year, long yday, long hour, long minute, double second,
long *gps_week, double *sec_of_week);
/*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
void main()
{
long gps_week, year, yday, hour, minute;
double sec_of_week, second;

gps_week = 633; sec_of_week = 241000.0;

gps_to_ydhms(gps_week, sec_of_week, &year, &yday, &hour, &minute, &second);
printf("%ld %lf %ld %ld %ld %ld %lf\n",
gps_week, sec_of_week, year, yday, hour, minute, second);
ydhms_to_gps(year, yday, hour, minute, second, &gps_week, &sec_of_week);
printf("%ld %lf %ld %ld %ld %ld %lf\n",
gps_week, sec_of_week, year, yday, hour, minute, second);
}
/*------------------------------------------------------------------------
* gps_to_ydhms *
* *
* Input: gps_week, sec_of_week *
* *
* Output: year, yday, hour, minute, second *
* *
* Author: Benjamin W. Remondi Date: November 1999 *
*-----------------------------------------------------------------------*/
void gps_to_ydhms(long gps_week, double sec_of_week,
long *year, long *yday, long *hour, long *minute, double *second)
{
long mjd, days_fr_jan1_1901;
double fmjd;
long delta_yrs, num_four_yrs, years_so_far, days_left;

mjd = gps_week*7 + sec_of_week/SEC_PER_DAY + JAN61980;
fmjd = fmod(sec_of_week, SEC_PER_DAY)/SEC_PER_DAY;

days_fr_jan1_1901 = mjd - JAN11901;
num_four_yrs = days_fr_jan1_1901/1461;
years_so_far = 1901 + 4*num_four_yrs;
days_left = days_fr_jan1_1901 - 1461*num_four_yrs;
delta_yrs = days_left/365 - days_left/1460;

*year = years_so_far + delta_yrs;
*yday = days_left - 365*delta_yrs + 1;
*hour = fmjd*24.0;
*minute = fmjd*1440.0 - *hour*60.0;
*second = fmjd*86400.0 - *hour*3600.0 - *minute*60.0;
}
/*------------------------------------------------------------------------
* ydhms_to_gps *
* *
* Input: year, yday, hour, minute, second *
* *
* Output: gps_week, sec_of_week *
* *
* Author: Benjamin W. Remondi Date: November 1999 *
*-----------------------------------------------------------------------*/
void ydhms_to_gps(long year, long yday, long hour, long minute, double second,
long *gps_week, double *sec_of_week)
{
long mjd;
double fmjd;

mjd = ((year - 1901)/4)*1461 + ((year - 1901)%4)*365 + yday - 1 + JAN11901;
fmjd = ((second/60.0 + minute)/60.0 + hour)/24.0;

*gps_week = (mjd - JAN61980)/7;
*sec_of_week = ( (mjd - JAN61980) - *gps_week*7 + fmjd )*SEC_PER_DAY;
}
/*============================= GPS_YMD.C ===============================*/
#include
#include

#define JAN61980 44244
#define JAN11901 15385
#define SEC_PER_DAY 86400.0

void gps_to_ymdhms(long gps_week, double sec_of_week, long *year,
long *month, long *mday, long *hour, long *minute, double *second);
void ymdhms_to_gps(long year, long month, long mday, long hour,
long minute, double second, long *gps_week, double *sec_of_week);
/*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
void main()
{
long gps_week;
long year, month, mday, hour, minute;
double sec_of_week, second;

gps_week = 842; sec_of_week = 475200.0;

gps_to_ymdhms(gps_week, sec_of_week, &year, &month, &mday, &hour, &minute, &second);
printf("%ld %lf %ld %ld %ld %ld %ld %lf\n",
gps_week, sec_of_week, year, month, mday, hour, minute, second);

gps_week = 0; sec_of_week = 0.0;
ymdhms_to_gps(year, month, mday, hour, minute, second, &gps_week, &sec_of_week);
printf("%ld %lf %ld %ld %ld %ld %ld %lf\n",
gps_week, sec_of_week, year, month, mday, hour, minute, second);
}
/*------------------------------------------------------------------------
* gps_to_ymdhms *
* *
* Input: gps_week, sec_of_week *
* *
* Output: year, month, mday, hour, minute, second *
* *
* Author: Benjamin W. Remondi Date: November 1999 *
*-----------------------------------------------------------------------*/
void gps_to_ymdhms(long gps_week, double sec_of_week, long *year,
long *month, long *mday, long *hour, long *minute, double *second)
{
static long month_day[2][13] = {
{0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365},
{0, 31, 60, 91, 121, 152, 182, 213, 244, 274, 305, 335, 366}
};
long leap, guess, more;
long yday, mjd, days_fr_jan1_1901;
long delta_yrs, num_four_yrs, years_so_far, days_left;
double fmjd;

mjd = gps_week*7 + sec_of_week/SEC_PER_DAY + JAN61980;
fmjd = fmod(sec_of_week, SEC_PER_DAY)/SEC_PER_DAY;

printf(" mjd = %ld fmjd = %16.14lf \n",mjd,fmjd);

days_fr_jan1_1901 = mjd - JAN11901;
num_four_yrs = days_fr_jan1_1901/1461;
years_so_far = 1901 + 4*num_four_yrs;
days_left = days_fr_jan1_1901 - 1461*num_four_yrs;
delta_yrs = days_left/365 - days_left/1460;

*year = years_so_far + delta_yrs;
yday = days_left - 365*delta_yrs + 1;
*hour = fmjd*24.0;
*minute = fmjd*1440.0 - *hour*60.0;
*second = fmjd*86400.0 - *hour*3600.0 - *minute*60.0;

leap = ( *year%4 == 0 );
guess = yday*0.032;
more = ( ( yday - month_day[leap][guess+1] ) > 0 );
*month = guess + more + 1;
*mday = yday - month_day[leap][guess+more];
}
/*------------------------------------------------------------------------
* ymdhms_to_gps *
* *
* Input: year, month, mday, hour, minute, second *
* *
* Output: gps_week, sec_of_week *
* *
* Author: Benjamin W. Remondi Date: November 1999 *
*-----------------------------------------------------------------------*/
void ymdhms_to_gps(long year, long month, long mday, long hour,
long minute, double second, long *gps_week, double *sec_of_week)
{
static long month_day[2][12] = {
{0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334},
{0, 31, 60, 91, 121, 152, 182, 213, 244, 274, 305, 335}
};
long yday, mjd, leap;
double fmjd;

leap = (year%4 == 0);
yday = month_day[leap][month-1] + mday;

mjd = ((year - 1901)/4)*1461 + ((year - 1901)%4)*365 + yday - 1 + JAN11901;
fmjd = ((second/60.0 + minute)/60.0 + hour)/24.0;

*gps_week = (mjd - JAN61980)/7;
*sec_of_week = ( (mjd - JAN61980) - *gps_week*7 + fmjd )*SEC_PER_DAY;
}
/*============================= MJD_GPS.C ===============================*/
#include
#include

#define JAN61980 44244
#define JAN11901 15385
#define SEC_PER_DAY 86400.0

void mjd_to_gps(long mjd, double fmjd, long *gps_week, double *sec_of_week);
void gps_to_mjd(long gps_week, double sec_of_week, long *mjd, double *fmjd);
/*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
void main()
{
long mjd=0, gps_week=0;
double fmjd=0.0, sec_of_week=0.0;

mjd = 48522; fmjd = 0.75;

printf("%ld %lf %ld %lf\n", mjd, fmjd, gps_week, sec_of_week);

mjd_to_gps(mjd, fmjd, &gps_week, &sec_of_week);
printf("%ld %lf %ld %lf\n", mjd, fmjd, gps_week, sec_of_week);

gps_week = 736; sec_of_week = 410000.0;

gps_to_mjd(gps_week, sec_of_week, &mjd, &fmjd);
printf("%ld %lf %ld %lf\n", mjd, fmjd, gps_week, sec_of_week);
}
/*------------------------------------------------------------------------
* mjd_to_gps *
* *
* Input: mjd, fmjd *
* *
* Output: gps_week, sec_of_week *
* *
* Author: Benjamin W. Remondi Date: November 1999 *
*-----------------------------------------------------------------------*/
void mjd_to_gps(long mjd, double fmjd, long *gps_week, double *sec_of_week)
{
*gps_week = (mjd - JAN61980)/7;
*sec_of_week = ( (mjd - JAN61980) - *gps_week*7 + fmjd )*SEC_PER_DAY;
}
/*------------------------------------------------------------------------
* gps_to_mjd *
* *
* Input: gps_week, sec_of_week *
* *
* Output: mjd, fmjd *
* *
* Author: Benjamin W. Remondi Date: November 1999 *
*-----------------------------------------------------------------------*/
void gps_to_mjd(long gps_week, double sec_of_week, long *mjd, double *fmjd)
{
*mjd = gps_week*7 + sec_of_week/SEC_PER_DAY + JAN61980;
*fmjd = fmod(sec_of_week, SEC_PER_DAY)/SEC_PER_DAY;
}
/*============================= MJD_YD.C ===============================*/
#include
#include

#define JAN61980 44244
#define JAN11901 15385
#define SEC_PER_DAY 86400.0

void mjd_to_ydhms(long mjd, double fmjd, long *year, long *yday,
long *hour, long *minute, double *second);
void ydhms_to_mjd(long year, long yday, long hour, long minute,
double second, long *mjd, double *fmjd);
/*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
void main()
{
long mjd, year, yday, hour, minute;
double fmjd, second;

mjd = 49400; fmjd = 0.65;
mjd_to_ydhms(mjd, fmjd, &year, &yday, &hour, &minute, &second);
printf("%ld %lf %ld %ld %ld %ld %lf\n",
mjd, fmjd, year, yday, hour, minute, second);
ydhms_to_mjd(year, yday, hour, minute, second, &mjd, &fmjd);
printf("%ld %lf %ld %ld %ld %ld %lf\n",
mjd, fmjd, year, yday, hour, minute, second);

}
/*------------------------------------------------------------------------
* mjd_to_ydhms *
* *
* Input: mjd, fmjd *
* *
* Output: year, yday, hour, minute, second *
* *
* Author: Benjamin W. Remondi Date: November 1999 *
*-----------------------------------------------------------------------*/
void mjd_to_ydhms(long mjd, double fmjd, long *year, long *yday,
long *hour, long *minute, double *second)
{
long days_fr_jan1_1901, delta_yrs, num_four_yrs, years_so_far, days_left;

days_fr_jan1_1901 = mjd - JAN11901;
num_four_yrs = days_fr_jan1_1901/1461;
years_so_far = 1901 + 4*num_four_yrs;
days_left = days_fr_jan1_1901 - 1461*num_four_yrs;
delta_yrs = days_left/365 - days_left/1460;

*year = years_so_far + delta_yrs;
*yday = days_left - 365*delta_yrs + 1;
*hour = fmjd*24.0;
*minute = fmjd*1440.0 - *hour*60.0;
*second = fmjd*86400.0 - *hour*3600.0 - *minute*60.0;
}
/*------------------------------------------------------------------------
* ydhms_to_mjd *
* *
* Input: year, yday, hour, minute, second *
* *
* Output: mjd, fmjd *
* *
* Author: Benjamin W. Remondi Date: November 1999 *
*-----------------------------------------------------------------------*/
void ydhms_to_mjd(long year, long yday, long hour, long minute,
double second, long *mjd, double *fmjd)
{
*mjd = ((year - 1901)/4)*1461 + ((year - 1901)%4)*365 + yday - 1 + JAN11901;
*fmjd = ((second/60.0 + minute)/60.0 + hour)/24.0;
}
/*============================= MJD_YMD.C ===============================*/
#include
#include

#define JAN61980 44244
#define JAN11901 15385
#define SEC_PER_DAY 86400.0

void mjd_to_ymdhms(long mjd, double fmjd, long *year, long *month,
long *mday, long *hour, long *minute, double *second);
void ymdhms_to_mjd(long year, long month, long mday, long hour, long minute,
double second, long *mjd, double *fmjd);
/*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
void main()
{
long mjd, year, month, mday, hour, minute;
double fmjd, second;

mjd = 48257; fmjd = 0.65;
mjd_to_ymdhms(mjd, fmjd, &year, &month, &mday, &hour, &minute, &second);
printf("%ld %lf %ld %ld %ld %ld %ld %lf\n",
mjd, fmjd, year, month, mday, hour, minute, second);

ymdhms_to_mjd(year, month, mday, hour, minute, second, &mjd, &fmjd);
printf("%ld %lf %ld %ld %ld %ld %ld %lf\n",
mjd, fmjd, year, month, mday, hour, minute, second);
}
/*------------------------------------------------------------------------
* mjd_to_ymdhms *
* *
* Input: mjd, fmjd *
* *
* Output: year, month, mday, hour, minute, second *
* *
* Author: Benjamin W. Remondi Date: November 1999 *
*-----------------------------------------------------------------------*/
void mjd_to_ymdhms(long mjd, double fmjd, long *year, long *month,
long *mday, long *hour, long *minute, double *second)
{
static long month_day[2][13] = {
{0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365},
{0, 31, 60, 91, 121, 152, 182, 213, 244, 274, 305, 335, 366}
};
long days_fr_jan1_1901, delta_yrs, num_four_yrs, years_so_far, days_left;
long yday, leap, guess, more;

days_fr_jan1_1901 = mjd - JAN11901;
num_four_yrs = days_fr_jan1_1901/1461;
years_so_far = 1901 + 4*num_four_yrs;
days_left = days_fr_jan1_1901 - 1461*num_four_yrs;
delta_yrs = days_left/365 - days_left/1460;

*year = years_so_far + delta_yrs;
yday = days_left - 365*delta_yrs + 1;
*hour = fmjd*24.0;
*minute = fmjd*1440.0 - *hour*60.0;
*second = fmjd*86400.0 - *hour*3600.0 - *minute*60.0;
leap = ( *year%4 == 0 );
guess = yday*0.032;
more = (( yday - month_day[leap][guess+1] ) > 0);
*month = guess + more + 1;
*mday = yday - month_day[leap][guess+more];
}
/*------------------------------------------------------------------------
* ymdhms_to_mjd *
* *
* Input: year, month, mday, hour, minute, second *
* *
* Output: mjd, fmjd *
* *
* Author: Benjamin W. Remondi Date: November 1999 *
*-----------------------------------------------------------------------*/
void ymdhms_to_mjd(long year, long month, long mday, long hour, long minute,
double second, long *mjd, double *fmjd)
{
static long month_day[2][12] = {
{0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334},
{0, 31, 60, 91, 121, 152, 182, 213, 244, 274, 305, 335}
};
long yday, leap;

leap = (year%4 == 0);
yday = (month_day[leap][month-1] + mday);
*mjd = ((year - 1901)/4)*1461 + ((year - 1901)%4)*365 + yday - 1 + JAN11901;
*fmjd = ((second/60.0 + minute)/60.0 + hour)/24.0;
}
/*============================= YD_MJD.C ===============================*/
#include
#include

void yday_to_mday(long year, long yday, long *month, long *mday);
void mday_to_yday(long year, long month, long mday, long *yday);
/*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
void main()
{
long year, yday, month, mday;

year = 1993; yday = 365;

yday_to_mday(year, yday, &month, &mday);
printf("%ld %ld %ld %ld\n", year, yday, month, mday);

mday_to_yday(year, month, mday, &yday);
printf("%ld %ld %ld %ld\n", year, yday, month, mday);

}
/*------------------------------------------------------------------------
* yday_to_mday *
* *
* Input: year, yday *
* *
* Output: month, mday *
* *
* Author: Benjamin W. Remondi Date: November 1999 *
*-----------------------------------------------------------------------*/
void yday_to_mday(long year, long yday, long *month, long *mday)
{
static long month_day[2][13] = {
{0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365},
{0, 31, 60, 91, 121, 152, 182, 213, 244, 274, 305, 335, 366}
};
long leap, guess, more;

leap = (year%4 == 0);
guess = yday*0.032;
more = (( yday - month_day[leap][guess+1] ) > 0);
*month = guess + more + 1;
*mday = yday - month_day[leap][guess+more];
}
/*------------------------------------------------------------------------
* mday_to_yday *
* *
* Input: year, month, mday *
* *
* Output: yday *
* *
* Author: Benjamin W. Remondi Date: November 1999 *
*-----------------------------------------------------------------------*/
void mday_to_yday(long year, long month, long mday, long *yday)
{
static long month_day[2][12] = {
{0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334},
{0, 31, 60, 91, 121, 152, 182, 213, 244, 274, 305, 335}
};
long leap;
leap = (year%4 == 0);
*yday = month_day[leap][month-1] + mday;
}
/*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/

Minimal Spanning Tree algorithm by V. Kevin .M. Whitney

/*
This file contains a driver program, the function spantree,
an example input file, and an example output file. Do not
attempt to compile the C source code listed here until you
copy the input and output files to spantree.in and
spantree.output and then remove those lines from the bottom
of this file.
*/


#include
#include
#include
#include

int spantree( double **graph, int **min_span_tree, int n,
int *p_num_of_edges, double *p_sum_of_edges);

FILE *in, *out;


#define npts 9

/*-------------------------------------------------------------------------
This is a driver program for testing the Minimal Spanning Tree function.

in File handle for input file called spantree.in
out File handle for output file called spantree.out
graph 2D array used to store the edge weights of the graph.
npts number of points to be connected by the minimal spanning tree (MST)
buf1 temporary string buffer
*p character pointer used for the string tokenizer
n_mst number of edges in the MST
sum_mst sum of the edge weights in the MST

min_span_tree 2D array output by function spantree(). It holds the "to" and
"from" indices for each edge in the MST.
-------------------------------------------------------------------------*/

int main()
{
int i,j, n_mst;
double **graph, sum_mst;
int **min_span_tree;
char names[npts][3];
char buf1[82];
char *p;


if( ( in = fopen("spantree.in","r") ) == NULL )
{
printf(" ERROR opening file spantree.in ! \n");
return(1);
}


if( ( out = fopen("spantree.out","w") ) == NULL )
{
printf(" ERROR opening file spantree.out ! \n");
return(1);
}

graph = malloc( (npts)*sizeof(double *));
for( i=0; i < npts; i++)
{
graph[i] = malloc( (npts)*sizeof(double) );
if (!graph[i]) {
printf("memory request failed for graph matrix ! \n");
exit(1);
}
}

min_span_tree = malloc( (npts - 1)*sizeof(int *));
for( i=0; i < npts - 1; i++)
{
min_span_tree[i] = malloc( (2)*sizeof(int) );
if (!min_span_tree[i]) {
printf("memory request failed for min_span_tree matrix ! \n");
exit(1);
}
}

/* Read in the two header lines at the top of the input file */
fgets(buf1,80,in);
printf("%s",buf1);
fgets(buf1,80,in);
printf("%s",buf1);


/* read in the 2D graph array */
for( i=0; i < npts; i++ )
{
fgets(buf1,80,in);
p = strtok(buf1," ");
strcpy(names[i],p);
j = 0;
do {
p = strtok('\0'," ");
if( p && j < npts )
{
graph[i][j] = atof(p);
j++;
}
} while(p);
}

for( i=0; i < npts; i++ )
{
printf("%-2s ",names[i]);
for( j=0; j < npts; j++ )
{
printf("%6.1lf ",graph[i][j]);
}
printf("\n");
} /* end of loop to read in "npts" lines of data from graph array */


/* write out column headings for the output file */
fprintf(out," ",names[i]);
for( i=0; i < npts; i++ )
fprintf(out," %-2s",names[i]);
fprintf(out,"\n");

/* output the 2D graph array */
for( i=0; i < npts; i++ )
{
fprintf(out,"%-2s ",names[i]);
for( j=0; j < npts; j++ )
{
fprintf(out,"%6.1lf ",graph[i][j]);
}
fprintf(out,"\n");
} /* end of loop to read in "npts" lines of data from graph array */


/* call the spantree function to find the minimal spanning tree */
i = spantree( graph, min_span_tree, npts, &n_mst, &sum_mst );
if( i != 0 ) printf(" Error returned from spantree: %d\n",i);


/* output the minimal spanning tree to the output file called spantree.out */
fprintf(out,"\n\n Minimal Spanning Tree: \n\n");
printf("\n\n Minimal Spanning Tree: \n\n");
for( i = 0; i < npts - 1; i++ )
{
fprintf(out," %2d %2d %-2s %-2s \n",min_span_tree[i][0],min_span_tree[i][1],
names[ min_span_tree[i][0] ], names[ min_span_tree[i][1] ] );
printf(" %2d %2d %-2s %-2s \n",min_span_tree[i][0],min_span_tree[i][1],
names[ min_span_tree[i][0] ], names[ min_span_tree[i][1] ] );
}
fprintf(out,"\n\n Number of edges in Minimal Spanning Tree: %d\n\n",n_mst);
printf("\n\n Number of edges in Minimal Spanning Tree: %d\n\n",n_mst);
fprintf(out,"\n\n Sum of edges in Minimal Spanning Tree: %lf\n\n",sum_mst);
printf("\n\n Sum of edges in Minimal Spanning Tree: %lf\n\n",sum_mst);

fclose(in);
fclose(out);

for( i=0; i < npts; i++)
free(graph[i]);
for( i=0; i < npts - 1; i++)
free(min_span_tree[i]);

return(0);
}

/*-------------------------------------------------------------------------
This is the spantree function.

int spantree( double **graph, int **min_span_tree, int n,
int *p_num_of_edges, double *p_sum_of_edges)

This C function is a modified version of a Fortran subroutine originally
published by V.K.M. Whitney in Communications of the Association for
Computing Machinery (ACM) in 1972, Algorithm 422 minimal spanning tree [H],
15(4), 273-274. The Fortran code has been recently digitized and is
available as file 422 from the ACM at http://www.acm.org/calgo/contents/.
Because the algorithm in this C code has been modified, the ACM is not
responsible for its accuracy. This C code may contain material copyrighted
by ACM. Please view the ACM copyright agreement at:
http://www.acm.org/pubs/copyright_policy/softwareCRnotice.html

Input variables
---------------
**graph 2D matrix holding representing the graph
n the number of nodes in the graph

Output variables
----------------
**min_span_tree 2D matrix holding the station indices for each edge
in the minimal spanning tree (MST).
*p_num_of_edges number of edges in the MST.
*p_sum_of_edges sum of all edge weights in the MST.

-------------------------------------------------------------------------*/

int spantree( double **graph, int **min_span_tree, int n,
int *p_num_of_edges, double *p_sum_of_edges)
{
int i,best_node,new_node,num_nodes_outside, num_of_edges;
int *closest_existing_node,*not_in_tree,outside_node;
int all_nodes_in_tree = 0;
double *smallest_edges, edge_weight, best_edge, sum_of_edges;

/* allocate memory for arrays */
closest_existing_node = malloc( (n)*sizeof(int) );
if (!closest_existing_node) {
printf(" In spantree, memory request failed for closest_existing_node matrix ! \n");
return(1);
}

not_in_tree = malloc( (n)*sizeof(int) );
if (!not_in_tree) {
printf(" In spantree, memory request failed for not_in_tree matrix ! \n");
return(2);
}

smallest_edges = malloc( (n)*sizeof(double) );
if (!smallest_edges) {
printf(" In spantree, memory request failed for smallest_edges matrix ! \n");
return(3);
}

/* initialize the node label arrays */
sum_of_edges = 0.0;
num_nodes_outside = n - 1;
new_node = n - 1; /* the last node is the first node in the MST */
num_of_edges = 0;

for( i = 0; i < num_nodes_outside; i++ )
{
not_in_tree[i] = i;
smallest_edges[i] = graph[i][new_node];
closest_existing_node[i] = new_node;
}

/* update labels of nodes not yet in tree */
while( !all_nodes_in_tree )
{
for( i = 0; i < num_nodes_outside; i++ )
{
outside_node = not_in_tree[i];
edge_weight = graph[outside_node][new_node];
if( smallest_edges[i] <= edge_weight ) continue;
smallest_edges[i] = edge_weight;
closest_existing_node[i] = new_node;
}

/* find node outside tree nearest to tree */
best_edge = smallest_edges[0]; /* to start, assume 1st edge is closest */
for( i = 0; i < num_nodes_outside; i++ )
{
if( smallest_edges[i] > best_edge ) continue;
best_edge = smallest_edges[i];
best_node = i;
}

/* put nodes of appropriate edge into array mst */
min_span_tree[num_of_edges][0] = not_in_tree[best_node];
min_span_tree[num_of_edges][1] = closest_existing_node[best_node];
sum_of_edges = sum_of_edges + best_edge;
new_node = not_in_tree[best_node];
num_of_edges++;

/* delete new tree node from array not_in_tree by replacing it with
the last node in not_in_tree[], then decrement the number of
nodes not yet in the tree */
smallest_edges[best_node] = smallest_edges[num_nodes_outside - 1];
not_in_tree[best_node] = not_in_tree[num_nodes_outside - 1];
closest_existing_node[best_node] = closest_existing_node[num_nodes_outside - 1];
num_nodes_outside--;
if( num_nodes_outside == 0 ) all_nodes_in_tree = num_of_edges;

} /* finish while loop when all nodes are in tree */

*p_num_of_edges = num_of_edges;
*p_sum_of_edges = sum_of_edges;

/* free memory */
free( closest_existing_node );
free( not_in_tree );
free( smallest_edges );

return(0);
}
============== spantree.in =================================================
Name Distances between cities in miles
---- ---------------------------------------------------------------------
A 0.0 60.2 62.6 68.9 114.4 68.9 124.8 136.5 83.6
B 60.2 0.0 122.6 31.3 70.8 67.8 180.4 120.7 32.9
C 62.6 122.6 0.0 126.2 168.4 108.8 79.6 170.4 145.2
D 68.9 31.3 126.2 0.0 46.2 42.4 193.6 89.4 60.9
E 114.4 70.8 168.4 46.2 0.0 65.7 239.0 68.8 89.3
F 68.9 67.8 108.8 42.4 65.7 0.0 185.1 67.6 100.4
G 124.8 180.4 79.6 193.6 239.0 185.1 0.0 249.2 192.5
H 136.5 120.7 170.4 89.4 68.8 67.6 249.2 0.0 148.5
I 83.6 32.9 145.2 60.9 89.3 100.4 192.5 148.5 0.0
============== spantree.output =============================================

A B C D E F G H I
A 0.0 60.2 62.6 68.9 114.4 68.9 124.8 136.5 83.6
B 60.2 0.0 122.6 31.3 70.8 67.8 180.4 120.7 32.9
C 62.6 122.6 0.0 126.2 168.4 108.8 79.6 170.4 145.2
D 68.9 31.3 126.2 0.0 46.2 42.4 193.6 89.4 60.9
E 114.4 70.8 168.4 46.2 0.0 65.7 239.0 68.8 89.3
F 68.9 67.8 108.8 42.4 65.7 0.0 185.1 67.6 100.4
G 124.8 180.4 79.6 193.6 239.0 185.1 0.0 249.2 192.5
H 136.5 120.7 170.4 89.4 68.8 67.6 249.2 0.0 148.5
I 83.6 32.9 145.2 60.9 89.3 100.4 192.5 148.5 0.0


Minimal Spanning Tree:

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


Number of edges in Minimal Spanning Tree: 8



Sum of edges in Minimal Spanning Tree: 422.800000

============== end of file span-c.txt ======================================