(CBSNews.com) - U.S. intelligence analysts were able to intercept rare communications by al Qaeda leaders who were openly discussing possible terror plots, CBS News learned Monday. The public acknowledgement of the interception, however, could very well tip off terrorists and prompt them to refrain from engaging in such discussions again, two senators warned Tuesday from Cairo, in an interview with CBS News' Clarrisa Ward.
"I'm very worried about leaks to the media of classified information because it warns the enemy," Sen. John McCain, R-Ariz., told Ward. "That'll be the last intercept of that kind, of means of communication that we intercept."
Added Sen. Lindsey Graham, R-S.C., "If we compromise our ability to find out what these guys are up to and stop them before they act, we'll pay a heavy price. They're not deterred by dying. They embrace dying. They just want to take me and you with 'em."
McCain and Graham are currently in Egypt, where they have urged the military-backed government to release political prisoners and move toward an open democracy.
While the U.S. is aiming to help settle the unrest in Egypt, it's also monitoring al Qaeda activity in Yemen, where al Qaeda in the Arabian Peninsula (AQAP) is based. Sources confirmed to CBS News that the intercepted electronic conversation occurred between the top leadership of core Al Qaeda in the tribal areas of Pakistan and the head of AQAP. The intercepted communications prompted the U.S. to close nearly two-dozen embassies and consulates around the world and order non-emergency staff of the U.S. Embassy in Yemen to leave the country.
While McCain said it could help the enemy to publicize the fact that their communications were intercepted, he added that the news may "remind some of my colleagues in the Congress that al Qaeda is not dead."
Intelligence-gathering efforts at the National Security Agency have come under fire lately for their broad nature, and McCain said here must be more transparency and accountability within the NSA. "But to abandon some of the practices that have proven to be successful in countering al Qaeda, well, would be a very serious mistake," he said.
Graham added that programs designed to monitor terrorist activity are already subject to oversight.
"If we can make it more stringent, fine, but the information we've gained from these programs and other programs we have in place, I believe has made us far safer," he said. "And any time you tell your enemy what you're doing and how you do it, that's a benefit to them and a detriment to us."
© 2013 CBS Interactive Inc. All Rights Reserved.