KIEV, Aug. 13 - Tensions between Russia and Ukraine rose on Wednesday after President Viktor Yushchenko signed two decrees de-facto restricting movements of the Russian Black Sea Fleet that had been stationed in Sevastopol.

The decrees were signed following an emergency conference call of the National Security and Defense Council, the country’s top security body.

Russia reacted angrily to the decrees, with the Foreign Ministry calling the move “a serious new anti-Russian step."

“The changes are aimed at creating serious complications for practical activity of the fleet in direct contradiction to agreements between Russia and Ukraine,” the ministry said.

“This is a unilateral step that deals a blow against [ongoing] negotiations over the Black Sea Fleet, while in a wider case it [affects] the entire complex of bilateral relations,” the ministry said.

The decrees require that “battleships and aircraft of the Black Sea Fleet may cross the Ukrainian border only after submitting a notice to the Ukrainian military chief of staff, but no later than 72 hours before the anticipated crossing of the border.”

The notice should also contain “the number of personnel on a battleship or an aircraft, as well as information about the weapons, munitions, explosives and other military property.”

At the same time, the personnel of the Black Sea Fleet must cross the border at special border crossing points, producing military ID or passport, while the Ukrainian immigration staff will be making special stamps, such as ‘Entry’ or ‘Departure.’

The new restrictions make it more difficult for the BSF battleships and personnel to cross the Ukrainian border, while the process becomes more time consuming.

There is at least 10,000 Russian military personnel currently at the BSF in Sevastopol, according to Ukrainian estimates.

The new border crossing regime for the BSF comes after Ukraine apparently decided there was no way to prevent Russian battleships from entering Ukraine, even if they had participated in the military conflict in Georgia.

Russia last week sent a flotilla of battleships from their naval base in Sevastopol towards the zone of fighting off the Georgian coast.

The flotilla, led by flag-ship Moskva, a battle-cruiser equipped with 16 cruise missiles capable of firing on targets within the range of 550-km, consisted of seven ships, including one transportation vessel and one rescue vessel.

The flotilla appeared off the Georgian coast on Sunday, but had been later relocated towards the Russian naval port of Novorossiisk in the Black Sea.

There were no indications that these battleships were used in the conflict, but Russia’s naval command had confirmed late Sunday that undisclosed Russian battleships had sunk one “target.”

Media reports said that Russian battleships had fired and sunk a Georgian gunboat after four such gunboats had apparently rushed towards the positions of Russian fleet.

According to an agreement signed in 1996, Russia is allowed to station its BSF in Sevastopol until 2017. Russia pays about $100 million to Ukraine annually for stationing the fleet.

Ukraine, which has been pressing to increase the rent for the stationing - perhaps to between $400 million and 1.5 billion annually - has recently indicated that it would not let Russia extend the agreement beyond 2017.

Russia said it hoped to station the battleships in Sevastopol beyond 2017. (tl/ez)